QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#808728 | #77. Dazzling Stars | LaVuna47 | WA | 283ms | 3928kb | C++17 | 3.8kb | 2024-12-11 00:45:59 | 2024-12-11 00:46:00 |
Judging History
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'