QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#808728#77. Dazzling StarsLaVuna47WA 283ms3928kbC++173.8kb2024-12-11 00:45:592024-12-11 00:46:00

Judging History

你现在查看的是最新测评结果

  • [2024-12-11 00:46:00]
  • 评测
  • 测评结果:WA
  • 用时:283ms
  • 内存:3928kb
  • [2024-12-11 00:45:59]
  • 提交

answer

/** gnu specific **/
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
/** contains everything I need in std **/
#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(S) ((int)S.size())
#define FOR(i, st_, n) for(int i = st_; i < n; ++i)
#define RFOR(i, n, end_) for(int i = (n)-1; i >= end_; --i)
#define x first
#define y second
#define pb push_back
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef unsigned long long ull;
typedef long double LD;
typedef pair<ull, ull> pull;
using namespace __gnu_pbds;
typedef tree<ll, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
using namespace std;
#ifdef ONPC
mt19937 rnd(228);
#else
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
#endif

struct Point
{
	ll x,y;
	ll b;
};

// Function to calculate the distance from point P to the line through points A and B
double distPointToLine(const Point& P, const Point& A, const Point& B)
{
    // Calculate the coefficients of the line equation Ax + By + C = 0
    double A_coeff = B.y - A.y;
    double B_coeff = A.x - B.x;
    double C_coeff = B.x * A.y - A.x * B.y;

    // Compute the numerator and denominator for the distance formula
    double numerator = std::abs(A_coeff * P.x + B_coeff * P.y + C_coeff);
    double denominator = std::sqrt(A_coeff * A_coeff + B_coeff * B_coeff);

    // Return the distance
    return numerator / denominator;
}

const LD EPS=1e-9;
int solve()
{
	int n;
	if(!(cin>>n))
		return 1;
	vector<Point> po(n);
	for(auto&[x,y,b]:po)cin>>x>>y>>b;
	if(n<=3)
	{
		cout<<"Y\n";
		return 0;
	}
	sort(all(po),[](const Point&p1, const Point& p2) -> bool{
		return p1.b < p2.b;
	});
	FOR(i,0,n-1)
	{
		{
			auto l1=po[i],l2=po[i+1];
			l1.x -= 1e6;
			l1.y -= 1e6;
			l2.x -= 1e6;
			l2.y -= 1e6;
			
			auto cur_po=po;
			sort(all(cur_po),[&](const Point& p1, const Point& p2){
				auto d1=distPointToLine(p1,l1,l2), d2=distPointToLine(p2,l1,l2);
				if(abs(d1-d2) < EPS)
				{
					return p1.b > p2.b;
				}
				return d1 < d2;
			});
			//cout << l1.x-1e6 << ' ' << l1.y-1e6 <<", "<< l2.x-1e6 << " " << l2.y-1e6 << '\n';
			//FOR(j,0,n)
			//{
				//cout << cur_po[j].b << ' ';
			//}
			//cout << '\n';
			bool ok=true;
			FOR(j,0,n-1)
			{
				if(cur_po[j].b < cur_po[j+1].b)
				{
					ok=false;
					break;
				}
			}
			if(ok)
			{
				cout<<"Y\n";
				return 0;
			}
		}
		{
			auto l1=po[i],l2=po[i+1];
			l1.x += 1e6;
			l1.y += 1e6;
			l2.x += 1e6;
			l2.y += 1e6;
			
			auto cur_po=po;
			sort(all(cur_po),[&](const Point& p1, const Point& p2){
				auto d1=distPointToLine(p1,l1,l2), d2=distPointToLine(p2,l1,l2);
				if(abs(d1-d2) < EPS)
				{
					return p1.b > p2.b;
				}
				return d1 < d2;
			});
			//cout << l1.x-1e6 << ' ' << l1.y-1e6 <<", "<< l2.x-1e6 << " " << l2.y-1e6 << '\n';
			//FOR(j,0,n)
			//{
				//cout << cur_po[j].b << ' ';
			//}
			//cout << '\n';
			bool ok=true;
			FOR(j,0,n-1)
			{
				if(cur_po[j].b < cur_po[j+1].b)
				{
					ok=false;
					break;
				}
			}
			if(ok)
			{
				cout<<"Y\n";
				return 0;
			}
		}
	}
	
	cout << "N\n";
    return 0;
}

int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int TET = 1e9;
    //cin >> TET;
    for (int i = 1; i <= TET; i++)
    {
        if (solve())
        {
            break;
        }
#ifdef ONPC
        cout << "__________________________" << endl;
#endif
    }
#ifdef ONPC
    cerr << endl << "finished in " << clock() * 1.0 / CLOCKS_PER_SEC << " sec" << endl;
#endif
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3692kb

input:

4
2 2 1
2 5 2
5 5 3
5 2 4

output:

Y

result:

ok single line: 'Y'

Test #2:

score: 0
Accepted
time: 281ms
memory: 3616kb

input:

1000
948 1040 5
8222 9897 5
227 -2641 5
7927 -779 5
8288 865 5
1626 -3327 5
3849 -6795 5
3468 7081 5
8003 -6418 5
4603 3061 5
7459 690 5
3780 -6692 5
1982 4037 5
9069 2764 5
248 -5372 5
7575 -3451 5
7273 2061 5
8378 2182 5
6238 406 5
1847 226 5
1704 1876 5
9124 7138 5
977 7813 5
1036 -5564 5
6767 -2...

output:

N

result:

ok single line: 'N'

Test #3:

score: 0
Accepted
time: 281ms
memory: 3924kb

input:

1000
9036 -6349 5
6133 5703 5
8367 1427 5
1537 9208 5
3228 -4348 5
8333 -8494 5
4478 -5274 5
6303 -4728 5
7738 5528 5
2640 4490 5
5299 -5419 5
1133 6527 5
372 -9371 5
6580 9569 5
7418 -2883 5
7573 4554 5
393 376 5
9460 9699 5
892 786 5
6536 -6410 5
1462 3072 5
5423 8491 5
9100 -6072 5
5269 9822 5
67...

output:

N

result:

ok single line: 'N'

Test #4:

score: 0
Accepted
time: 275ms
memory: 3624kb

input:

1000
9263 -7525 1
-5466 150 1
-8518 -4390 1
5702 -1323 1
8981 -1622 1
903 -7326 1
-844 -3052 1
4148 -5766 1
7979 -7727 1
5 -4715 1
2239 -884 1
-1344 -5032 1
-932 -1722 1
-6695 -5274 1
-278 -1415 1
-9078 -8502 1
-7945 -1334 1
5504 -1435 1
-9357 -8067 1
4386 -8413 1
1577 -9107 1
-6159 317 1
-5868 -514...

output:

N

result:

ok single line: 'N'

Test #5:

score: 0
Accepted
time: 280ms
memory: 3676kb

input:

1000
-971 -9339 1
-1956 -7584 1
7043 -2269 1
6492 -3865 1
-1480 -8110 1
-364 -8582 1
3586 -7905 1
-3961 -3949 1
-3568 -6167 1
-6335 -8104 1
-158 -3928 1
7886 -8912 1
-2571 -3072 1
8982 -3802 1
-7862 -7163 1
9088 -1655 1
2170 -1927 1
6843 -8537 1
-6884 -4769 1
-4606 -4289 1
-4458 -5559 1
-3028 -6900 ...

output:

N

result:

ok single line: 'N'

Test #6:

score: 0
Accepted
time: 275ms
memory: 3624kb

input:

1000
-2334 -538 1
-2211 -310 1
-4272 -2431 1
-1993 -2574 1
-620 -335 1
-6709 -5317 1
-9033 -8951 1
-8340 -6504 1
-2564 -4288 1
-2416 -9241 1
-5061 -4959 1
-3004 -1178 1
-2390 -2504 1
-852 -5459 1
-9465 -1856 1
-1640 -8885 1
-4302 -9766 1
-8651 -4712 1
87 -9246 1
-393 -477 1
-7778 -1788 1
-7017 -8538...

output:

N

result:

ok single line: 'N'

Test #7:

score: 0
Accepted
time: 277ms
memory: 3684kb

input:

1000
731 -9300 1
-3767 -6206 1
-6851 821 1
-2961 -5587 1
-7568 -8064 1
-1425 -3676 1
-4294 -9579 1
934 -7095 1
-7794 -8535 1
-6731 -923 1
-8911 -9323 1
-2960 -2239 1
-7014 -7463 1
-5756 -8529 1
-1797 -3816 1
-1951 -9757 1
-4968 -9757 1
-2442 -8465 1
-5161 -4958 1
-1030 -2386 1
-3469 256 1
-3336 -642...

output:

N

result:

ok single line: 'N'

Test #8:

score: 0
Accepted
time: 283ms
memory: 3684kb

input:

1000
1518 -4880 5
-373 2995 5
609 2542 5
531 -2584 5
-1438 2686 5
4447 -2167 5
-2036 3142 5
-347 -4356 5
640 4035 5
3644 -1407 5
2171 391 5
-3562 -2510 5
88 4088 5
2540 -4970 5
4778 -868 5
-3538 -2415 5
2780 -2634 5
2265 -177 5
-4458 1460 5
-689 2663 5
438 772 5
1125 -769 5
-2145 -2133 5
-3591 1827 ...

output:

N

result:

ok single line: 'N'

Test #9:

score: 0
Accepted
time: 283ms
memory: 3668kb

input:

1000
2136 9955 141
7046 -7009 417
7919 -4006 682
-8469 7209 468
-9927 -7095 462
5713 1169 975
-8181 -1752 83
6743 4766 992
-9882 7704 145
-5506 -8143 343
5766 -3022 563
4411 6761 559
775 -2033 752
-580 9394 926
-4240 9699 924
1171 8031 313
268 2198 239
6072 5218 358
-4695 6064 304
-5158 938 46
-7325...

output:

N

result:

ok single line: 'N'

Test #10:

score: 0
Accepted
time: 283ms
memory: 3928kb

input:

1000
1942 -3686 230
-6143 -6212 112
7753 -3753 891
-5482 -380 102
-4603 -8150 169
996 8522 144
-7001 4115 364
-3555 4073 480
-456 -235 281
-989 -6726 531
5694 1645 863
6120 6585 557
-5943 8253 111
-9189 2198 705
6341 -1170 700
6463 3995 701
-9648 496 548
-3740 -2495 604
6897 4819 611
-1282 -9648 803...

output:

N

result:

ok single line: 'N'

Test #11:

score: 0
Accepted
time: 283ms
memory: 3716kb

input:

1000
-7874 7742 265
-9073 5739 940
-9282 -7936 909
1294 -1058 462
-5293 3412 59
-6675 4016 651
-4277 -8585 498
8965 2616 390
-8023 -6847 78
8332 5827 560
8410 8187 242
7441 -6392 917
336 -8543 486
2821 -6930 90
-87 2442 432
7662 6777 455
4153 -8767 201
-780 5554 619
-6873 3747 877
-4851 3288 556
-46...

output:

N

result:

ok single line: 'N'

Test #12:

score: 0
Accepted
time: 0ms
memory: 3564kb

input:

4
1 -10000 1
-10000 0 100
0 10000 500
10000 0 1000

output:

N

result:

ok single line: 'N'

Test #13:

score: 0
Accepted
time: 57ms
memory: 3652kb

input:

468
-2534 -7230 867
-9872 56 899
-8384 1085 617
-9183 -2420 704
-960 4502 158
-5240 -7781 507
8477 1809 775
-2327 4922 102
-4177 3485 726
-1565 -8246 267
-5802 -4377 810
-6011 7728 880
-8905 -2424 492
-9531 -1506 907
-7759 1937 122
1574 7906 204
-9835 -8330 540
-9651 -8304 497
8419 -1598 399
2774 -8...

output:

N

result:

ok single line: 'N'

Test #14:

score: 0
Accepted
time: 2ms
memory: 3608kb

input:

86
-5352 2203 12
-5424 -2635 106
8870 379 364
-2712 -7797 603
3351 4933 863
7287 -2543 231
-8168 3881 644
-7783 4400 887
-9413 2552 779
4787 -4535 377
-8308 -5584 580
7892 -3176 665
8733 4274 215
-3360 8670 16
-147 -2703 177
1226 -3727 275
6520 4040 888
-9912 6115 473
62 8395 524
7983 5855 71
7363 -...

output:

N

result:

ok single line: 'N'

Test #15:

score: 0
Accepted
time: 188ms
memory: 3660kb

input:

825
-9765 -664 323
-8494 -8859 741
-9279 3189 59
-6668 -1064 723
4127 -1481 509
2637 -9025 416
-324 -9772 517
106 4094 127
6362 2895 343
-9397 6636 647
9898 9506 254
2437 -202 783
-1576 1169 54
8495 -8931 474
6243 -5646 284
3076 -8265 501
9732 -4610 728
207 -1647 495
9652 -7361 578
-2903 -7289 317
7...

output:

N

result:

ok single line: 'N'

Test #16:

score: 0
Accepted
time: 0ms
memory: 3624kb

input:

9
3 -6 1
2 2 3
-9 -3 1
7 -10 3
0 6 3
5 -6 2
-1 1 1
-3 -2 1
7 10 2

output:

N

result:

ok single line: 'N'

Test #17:

score: 0
Accepted
time: 0ms
memory: 3864kb

input:

9
-8 -6 2
0 8 2
5 -3 1
-8 -7 2
6 -6 1
-6 -2 3
-1 4 2
3 -2 2
4 4 1

output:

N

result:

ok single line: 'N'

Test #18:

score: 0
Accepted
time: 0ms
memory: 3688kb

input:

10
-6 -1 2
-4 -8 1
3 6 3
8 -8 2
7 0 2
-6 -5 1
4 4 3
10 -3 3
-2 -7 1
-6 -6 1

output:

Y

result:

ok single line: 'Y'

Test #19:

score: 0
Accepted
time: 0ms
memory: 3580kb

input:

10
10 -7 3
-5 -7 1
7 -1 1
0 -2 2
-4 -6 2
5 2 2
-1 -10 2
-1 -6 3
-4 4 3
3 6 1

output:

N

result:

ok single line: 'N'

Test #20:

score: 0
Accepted
time: 0ms
memory: 3668kb

input:

10
-9 8 3
7 7 3
1 -3 3
8 -10 1
7 -10 2
5 5 3
-3 -2 1
-1 8 3
-6 -3 1
-4 1 1

output:

N

result:

ok single line: 'N'

Test #21:

score: 0
Accepted
time: 0ms
memory: 3804kb

input:

5
-10 -8 1
-3 -9 3
-4 1 2
-3 6 3
3 -9 2

output:

N

result:

ok single line: 'N'

Test #22:

score: 0
Accepted
time: 0ms
memory: 3628kb

input:

9
-4 5 2
-1 7 3
-6 3 2
-10 10 1
9 -5 3
5 3 2
10 1 2
3 -9 2
-2 10 2

output:

N

result:

ok single line: 'N'

Test #23:

score: -100
Wrong Answer
time: 0ms
memory: 3604kb

input:

4
-200 -100 5
-100 -100 9
-100 -200 5
-200 -200 9

output:

Y

result:

wrong answer 1st lines differ - expected: 'N', found: 'Y'