結果
| 問題 |
No.2173 Nightcord
|
| コンテスト | |
| ユーザー |
 rin204
|
| 提出日時 | 2022-12-25 01:24:56 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 6,526 bytes |
| コンパイル時間 | 2,122 ms |
| コンパイル使用メモリ | 214,268 KB |
| 最終ジャッジ日時 | 2025-02-09 20:33:34 |
|
ジャッジサーバーID （参考情報） |
judge3 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 46 WA * 8 |
ソースコード
#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 = 0;
ll yy = 0;
for(int i = 0; i < lb; i++){
xx += B[i].x;
yy += B[i].y;
}
xx /= lb;
yy /= lb;
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 = 0;
yy = 0;
for(int i = 0; i < lb; i++){
xx += B[i].x;
yy += B[i].y;
}
xx /= lb;
yy /= lb;
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;
pi = acos(-1);
pi2 = 2 * pi;
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;
}