結果
問題 | No.2173 Nightcord |
ユーザー | 👑 rin204 |
提出日時 | 2022-12-25 01:33:21 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 6,341 bytes |
コンパイル時間 | 2,858 ms |
コンパイル使用メモリ | 219,536 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-04-29 07:22:07 |
合計ジャッジ時間 | 4,773 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | AC | 2 ms
5,376 KB |
testcase_03 | AC | 3 ms
5,376 KB |
testcase_04 | AC | 2 ms
5,376 KB |
testcase_05 | AC | 3 ms
5,376 KB |
testcase_06 | AC | 2 ms
5,376 KB |
testcase_07 | AC | 2 ms
5,376 KB |
testcase_08 | AC | 3 ms
5,376 KB |
testcase_09 | AC | 7 ms
5,376 KB |
testcase_10 | AC | 3 ms
5,376 KB |
testcase_11 | AC | 3 ms
5,376 KB |
testcase_12 | AC | 3 ms
5,376 KB |
testcase_13 | AC | 3 ms
5,376 KB |
testcase_14 | AC | 324 ms
5,376 KB |
testcase_15 | AC | 3 ms
5,376 KB |
testcase_16 | AC | 10 ms
5,376 KB |
testcase_17 | AC | 5 ms
5,376 KB |
testcase_18 | AC | 2 ms
5,376 KB |
testcase_19 | AC | 2 ms
5,376 KB |
testcase_20 | AC | 2 ms
5,376 KB |
testcase_21 | AC | 7 ms
5,376 KB |
testcase_22 | AC | 7 ms
5,376 KB |
testcase_23 | AC | 2 ms
5,376 KB |
testcase_24 | AC | 9 ms
5,376 KB |
testcase_25 | AC | 3 ms
5,376 KB |
testcase_26 | AC | 9 ms
5,376 KB |
testcase_27 | AC | 3 ms
5,376 KB |
testcase_28 | AC | 3 ms
5,376 KB |
testcase_29 | AC | 4 ms
5,376 KB |
testcase_30 | AC | 3 ms
5,376 KB |
testcase_31 | AC | 5 ms
5,376 KB |
testcase_32 | WA | - |
testcase_33 | AC | 3 ms
5,376 KB |
testcase_34 | AC | 3 ms
5,376 KB |
testcase_35 | AC | 3 ms
5,376 KB |
testcase_36 | AC | 2 ms
5,376 KB |
testcase_37 | AC | 3 ms
5,376 KB |
testcase_38 | WA | - |
testcase_39 | WA | - |
testcase_40 | AC | 3 ms
5,376 KB |
testcase_41 | AC | 2 ms
5,376 KB |
testcase_42 | WA | - |
testcase_43 | AC | 2 ms
5,376 KB |
testcase_44 | WA | - |
testcase_45 | AC | 2 ms
5,376 KB |
testcase_46 | WA | - |
testcase_47 | AC | 2 ms
5,376 KB |
testcase_48 | WA | - |
testcase_49 | AC | 2 ms
5,376 KB |
testcase_50 | WA | - |
testcase_51 | AC | 3 ms
5,376 KB |
testcase_52 | AC | 2 ms
5,376 KB |
testcase_53 | AC | 2 ms
5,376 KB |
testcase_54 | AC | 3 ms
5,376 KB |
testcase_55 | AC | 2 ms
5,376 KB |
testcase_56 | AC | 2 ms
5,376 KB |
ソースコード
#line 1 "A.cpp" // #pragma GCC target("avx2") // #pragma GCC optimize("O3") // #pragma GCC optimize("unroll-loops") #include<bits/stdc++.h> using namespace std; using ll = long long; #define endl "\n" void print(){ cout << '\n'; } template <class Head, class... Tail> void print(Head &&head, Tail &&... tail) { cout << head; if (sizeof...(Tail)) cout << ' '; print(forward<Tail>(tail)...); } template<typename T> void print(vector<T> &A){ int n = A.size(); for(int i = 0; i < n; i++){ cout << A[i]; if(i == n - 1) cout << '\n'; else cout << ' '; } } template<typename T, typename S> void prisep(vector<T> &A, S sep){ int n = A.size(); for(int i = 0; i < n; i++){ cout << A[i]; if(i == n - 1) cout << '\n'; else cout << sep; } } template<typename T> void print(vector<vector<T>> &A){ for(auto &row: A) print(row); } #line 2 "Library/C++/geometry/Point.hpp" struct Point{ long long x; long long y; Point(){} Point(long long x, long long y) : x(x), y(y) {} int area(){ if(y < 0){ if(x < 0) return 1; else return 2; } else{ if(x >= 0) return 3; else return 4; } } bool operator<(Point& rhs){ int ap = area(); int aq = rhs.area(); if(ap == aq){ if (x == 0 && y == 0) return true; return x * rhs.y > rhs.x * y; } else{ return ap < aq; } } }; #line 3 "Library/C++/geometry/cross3.hpp" long long cross3(Point &a, Point &b, Point &c){ return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x); } #line 4 "Library/C++/geometry/convexHull.hpp" vector<Point> convexHull(vector<Point> P, bool multi=true){ sort(P.begin(), P.end(), [](Point &l, Point &r){ if(l.x == r.x) return l.y < r.y; return l.x < r.x; }); vector<Point> Q; int n = P.size(); if(multi){ for(auto p:P){ while(Q.size() > 1 && cross3(Q[Q.size() - 1], Q[Q.size() - 2], p) > 0){ Q.pop_back(); } Q.push_back(p); } int t = Q.size(); for(int i = n - 2; i >= 0; i--){ Point p = P[i]; while(Q.size() > t && cross3(Q[Q.size() - 1], Q[Q.size() - 2], p) > 0){ Q.pop_back(); } Q.push_back(p); } } else{ for(auto p:P){ while(Q.size() > 1 && cross3(Q[Q.size() - 1], Q[Q.size() - 2], p) >= 0){ Q.pop_back(); } Q.push_back(p); } int t = Q.size(); for(int i = n - 2; i >= 0; i--){ Point p = P[i]; while(Q.size() > t && cross3(Q[Q.size() - 1], Q[Q.size() - 2], p) >= 0){ Q.pop_back(); } Q.push_back(p); } } Q.pop_back(); return Q; } #line 46 "A.cpp" void solve(){ int n, k; cin >> n >> k; vector<Point> R, B; int x, y, c; for(int i = 0; i < n; i++){ cin >> x >> y >> c; if(c == 1) R.push_back({x, y}); else B.push_back({x, y}); } if(R.size() == 0 || B.size() == 0){ print("No"); return; } if(R.size() > B.size()) swap(R, B); int lr = R.size(); int lb = B.size(); auto dist=[&](Point a, Point b){ ll dx = a.x - b.x; ll dy = a.y - b.y; return dx * dx + dy * dy; }; if(lr == 1){ for(int i = 0; i < lb; i++){ for(int j = i + 1; j < lb; j++){ auto x = cross3(B[i], B[j], R[0]); if(x == 0 && (dist(B[i], B[j]) >= dist(B[i], R[0])) && (dist(B[i], B[j]) >= dist(B[j], R[0]))){ print("Yes"); return; } } } } if(k == 3){ print("No"); return; } auto BB = B; B = convexHull(B, false); lb = B.size(); for(int i = 0; i < lr; i++){ bool in_ = true; bool same = (cross3(B[lb - 1], B[0], R[i]) >= 0); for(int j = 0; j < lb - 1; j++){ bool flg = (cross3(B[j], B[j + 1], R[i]) >= 0); if(flg != same){ in_ = false; break; } } if(in_){ print("Yes"); return; } } if(lr == 1){ print("No"); return; } ll xx = B[0].x; ll yy = B[0].y; for(int i = 0; i < lr; i++){ R[i].x -= xx; R[i].y -= yy; } for(int i = 0; i < lb; i++){ B[i].x -= xx; B[i].y -= yy; } for(int i = 0; i < BB.size(); i++){ BB[i].x -= xx; BB[i].y -= yy; } sort(R.begin(), R.end()); int r = 0; long double pi = acos(-1); long double pi2 = 2 * pi; auto cross=[&](Point &a, Point &b, Point &c, Point &d){ bool flg1 = __int128_t(cross3(a, b, c)) * __int128_t(cross3(a, b, d)) <= 0; bool flg2 = __int128_t(cross3(c, d, a)) * __int128_t(cross3(c, d, b)) <= 0; return bool(flg1 && flg2); }; for(int l = 0; l < lr; l++){ while(1){ long double d = atan2(R[r].y, R[r].x) - atan2(R[l].y, R[l].x); if(d <= 0) d += pi2; if(d < pi){ r++; if(r == lr) r = 0; } else{ break; } } for(int rr = r - 10; rr <= r + 10; rr++){ int br = (rr % lr + lr) % lr; if(cross(R[l], R[br], B[0], B[lb - 1])){ print("Yes"); return; } for(int j = 0; j < lb - 1; j++){ if(cross(R[l], R[br], B[j], B[j + 1])){ print("Yes"); return; } } } } swap(B, BB); swap(B, R); lr = R.size(); B = convexHull(B, false); lb = B.size(); for(int i = 0; i < lr; i++){ bool in_ = true; bool same = (cross3(B[lb - 1], B[0], R[i]) >= 0); for(int j = 0; j < lb - 1; j++){ bool flg = (cross3(B[j], B[j + 1], R[i]) >= 0); if(flg != same){ in_ = false; break; } } if(in_){ print("Yes"); return; } } xx = B[0].x; yy = B[0].y; for(int i = 0; i < lr; i++){ R[i].x -= xx; R[i].y -= yy; } for(int i = 0; i < lb; i++){ B[i].x -= xx; B[i].y -= yy; } sort(R.begin(), R.end()); r = 0; for(int l = 0; l < lr; l++){ while(1){ long double d = atan2(R[r].y, R[r].x) - atan2(R[l].y, R[l].x); if(d <= 0) d += pi2; if(d < pi){ r++; if(r == lr) r = 0; } else{ break; } } for(int rr = r - 10; rr <= r + 10; rr++){ int br = (rr % lr + lr) % lr; if(cross(R[l], R[br], B[0], B[lb - 1])){ print("Yes"); return; } for(int j = 0; j < lb - 1; j++){ if(cross(R[l], R[br], B[j], B[j + 1])){ print("Yes"); return; } } } } print("No"); } int main(){ cin.tie(0)->sync_with_stdio(0); int t; t = 1; // cin >> t; while(t--) solve(); return 0; }