結果
問題 | No.2173 Nightcord |
ユーザー |
![]() |
提出日時 | 2022-12-25 07:16:47 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,610 ms / 2,525 ms |
コード長 | 8,513 bytes |
コンパイル時間 | 2,582 ms |
コンパイル使用メモリ | 215,316 KB |
最終ジャッジ日時 | 2025-02-09 20:42:14 |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 54 |
コンパイルメッセージ
main.cpp: In function ‘int geti()’: main.cpp:25:23: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 25 | int geti(){int x;scanf("%d",&x);return x;} | ~~~~~^~~~~~~~~ main.cpp: In member function ‘void Solver::solve()’: main.cpp:181:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 181 | scanf("%d%d",&n,&k); | ~~~~~^~~~~~~~~~~~~~ main.cpp:185:12: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 185 | scanf("%d%d%d",&x,&y,&c); | ~~~~~^~~~~~~~~~~~~~~~~~~
ソースコード
#include <bits/stdc++.h> #define rep(i,n) for(int i = 0; i < (n); ++i) #define rep1(i,n) for(int i = 1; i <= (n); ++i) #define drep(i,n) for(int i = (n)-1; i >= 0; --i) #define srep(i,s,t) for (int i = s; i < (t); ++i) #define rng(a) a.begin(),a.end() #define rrng(a) a.rbegin(),a.rend() #define fi first #define se second #define pb push_back #define eb emplace_back #define pob pop_back #define sz(x) (int)(x).size() #define pcnt __builtin_popcountll #define snuke srand((unsigned)clock()+(unsigned)time(NULL)); #define newline puts("") using namespace std; template<typename T> using vc = vector<T>; template<typename T> using vv = vc<vc<T>>; template<typename T> using PQ = priority_queue<T,vc<T>,greater<T>>; using uint = unsigned; using ull = unsigned long long; using vi = vc<int>; using vvi = vv<int>; using vvvi = vv<vi>; using ll = long long; using vl = vc<ll>; using vvl = vv<ll>; using vvvl = vv<vl>; using P = pair<int,int>; using vp = vc<P>; using vvp = vv<P>; int geti(){int x;scanf("%d",&x);return x;} vi pm(int n, int s=0) { vi a(n); iota(rng(a),s); return a;} template<typename T>istream& operator>>(istream&i,vc<T>&v){rep(j,sz(v))i>>v[j];return i;} template<typename T>string join(const T&v,const string& d=""){stringstream s;rep(i,sz(v))(i?s<<d:s)<<v[i];return s.str();} template<typename T>ostream& operator<<(ostream&o,const vc<T>&v){if(sz(v))o<<join(v," ");return o;} template<typename T1,typename T2>istream& operator>>(istream&i,pair<T1,T2>&v){return i>>v.fi>>v.se;} template<typename T1,typename T2>ostream& operator<<(ostream&o,const pair<T1,T2>&v){return o<<v.fi<<","<<v.se;} template<typename T1,typename T2>void operator--(pair<T1,T2>&a,int){a.fi--;a.se--;} template<typename T>void operator--(vc<T>&a,int){for(T&x:a)x--;} template<typename T>void operator++(vc<T>&a,int){for(T&x:a)x++;} template<typename T>void operator+=(vc<T>&a,T b){for(T&x:a)x+=b;} template<typename T>void operator+=(vc<T>&a,const vc<T>&b){a.insert(a.end(),rng(b));} template<typename T1,typename T2>bool mins(T1& x,const T2&y){if(x>y){x=y;return true;}else return false;} template<typename T1,typename T2>bool maxs(T1& x,const T2&y){if(x<y){x=y;return true;}else return false;} template<typename Tx, typename Ty>Tx dup(Tx x, Ty y){return (x+y-1)/y;} template<typename T>ll suma(const vc<T>&a){ll res(0);for(auto&&x:a)res+=x;return res;} template<typename T>ll suma(const vv<T>&a){ll res(0);for(auto&&x:a)res+=suma(x);return res;} template<typename T>void uni(T& a){sort(rng(a));a.erase(unique(rng(a)),a.end());} template<typename T>void prepend(vc<T>&a,const T&x){a.insert(a.begin(),x);} const double eps = 1e-10; const ll LINF = 1001002003004005006ll; const int INF = 1001001001; #define dame { puts("-1"); return;} #define yes { puts("Yes"); return;} #define no { puts("No"); return;} #define ret(x) { cout<<(x)<<endl; return;} #define yn {puts("Yes");}else{puts("No");} const int MX = 200005; // Fraction struct frac { ll a, b; frac(ll _a=0, ll _b=1): a(_a), b(_b) { if (b == 0) a = 1; else if (b < 0) a = -a, b = -b; ll g = gcd(abs(a),b); a /= g; b /= g; } ll gcd(ll x, ll y) { return y?gcd(y,x%y):x;} frac inv() const { return frac(b,a);} frac operator+(const frac& x) const { return frac(a*x.b + x.a*b, b*x.b);} frac operator-(const frac& x) const { return frac(a*x.b - x.a*b, b*x.b);} frac operator*(const frac& x) const { return frac(a*x.a, b*x.b);} frac operator/(const frac& x) const { return frac(a*x.b, b*x.a);} frac& operator+=(const frac& x) { return *this = *this + x;} frac& operator-=(const frac& x) { return *this = *this - x;} frac& operator*=(const frac& x) { return *this = *this * x;} frac& operator/=(const frac& x) { return *this = *this / x;} bool operator<(const frac& x) const { return a*x.b < x.a*b;} bool operator==(const frac& x) const { return a == x.a && b == x.b;} bool operator!=(const frac& x) const { return a != x.a || b != x.b;} }; istream& operator>>(istream&i,frac&a){i>>a.a>>a.b;return i;} ostream& operator<<(ostream&o,const frac&a){o<<a.a<<"/"<<a.b;return o;} // // geom struct V { ll x, y; V(ll x=0, ll y=0):x(x),y(y){} V operator+(const V& t) const { return V(x+t.x,y+t.y);} V operator-(const V& t) const { return V(x-t.x,y-t.y);} V operator*(ll t) const { return V(x*t,y*t);} V operator/(ll t) const { return V(x/t,y/t);} V operator*(const V& t) const { return V(x*t.x-y*t.y,x*t.y+y*t.x);} V operator/(const V& t) const { return *this*V(t.x,-t.y)/t.norm2();} V& operator+=(const V& t) { x += t.x; y += t.y; return *this;} V& operator-=(const V& t) { x -= t.x; y -= t.y; return *this;} V& operator*=(ll t) { x *= t; y *= t; return *this;} V& operator/=(ll t) { x /= t; y /= t; return *this;} V& operator*=(const V& t) { return *this = *this*t;} V& operator/=(const V& t) { return *this = *this/t;} ll dot(const V& t) const { return x*t.x + y*t.y;} ll cross(const V& t) const { return x*t.y - y*t.x;} ll norm2() const { return x*x + y*y;} double norm() const { return sqrt(x*x + y*y);} V rev() const { return V(-x,-y);} V rotate90() const { return V(-y,x);} bool operator<(const V& a) const { return x != a.x ? x < a.x : y < a.y;} bool operator==(const V& a) const { return x == a.x && y == a.y;} int side() const { if (!y) return !x ? 0 : (x > 0 ? 1 : 3); return y > 0 ? 2 : 4; } // bool operator<(const V& a) const { // int s = side(), sa = a.side(); // if (s != sa) return s < sa; // return cross(a) > 0; // } }; istream& operator>>(istream&i,V&a){i>>a.x>>a.y;return i;} ostream& operator<<(ostream&o,const V&a){o<<a.x<<','<<a.y;return o;} struct Line { V s, t; Line(V s=V(0,0), V t=V(0,0)):s(s),t(t){} V dir() const { return t-s;} ll norm2() const { return dir().norm2();} double norm() const { return dir().norm();} /* +1: s-t,s-p : ccw * -1: s-t,s-p : cw * +2: t-s-p * -2: s-t-p * 0: s-p-t */ int ccw(const V& p) const { if (dir().cross(p-s) > 0) return +1; if (dir().cross(p-s) < 0) return -1; if (dir().dot(p-s) == 0) return +2; if (dir().norm2() < (p-s).norm2()) return -2; return 0; } bool touch(const Line& l) const { int a = ccw(l.s)*ccw(l.t), b = l.ccw(s)*l.ccw(t); return !a || !b || (a == -1 && b == -1); } }; using Poly = vector<V>; inline V pnxt(Poly& p, int i) { return p[(i+1)%sz(p)];} inline V ppre(Poly& p, int i) { return p[(i-1+sz(p))%sz(p)];} inline Line pline(Poly& p, int i) { return Line(p[i],pnxt(p,i));} Poly conv(Poly a) { // cw int n = sz(a); if (n <= 2) return a; sort(rng(a)); Poly res(n*2); int k = 0; for (int i = 0; i < n; ++i){ while (k > 1 && Line(res[k-1],res[k-2]).ccw(a[i]) != 1) --k; // <= -1 ok line res[k++] = a[i]; } int pre = k; for (int i = n - 2; 0 <= i; --i){ while (k > pre && Line(res[k-1],res[k-2]).ccw(a[i]) != 1) --k; // <= -1 ok line res[k++] = a[i]; } res.resize(k-1); return res; } ll area2(Poly& a) { ll res = 0; rep(i,sz(a)-2){ res += abs(V(a[i+1]-a[0]).cross(V(a[i+2]-a[0]))); } return res; // area*2 } struct Circle { V o; ll r; Circle(V o=V(0,0), ll r=0):o(o),r(r){} bool in(V p) { return (p-o).norm2() < r*r;} bool touch(Circle c) { return (c.o-o).norm2() < (c.r+r)*(c.r+r);} }; // geom struct Solver { void solve() { int n,k; scanf("%d%d",&n,&k); vc<Poly> p(2); rep(i,n) { int x,y,c; scanf("%d%d%d",&x,&y,&c); p[c-1].eb(x,y); } Poly a = p[0], b = p[1]; Poly ca = conv(a), cb = conv(b); rep(ri,2) { int na = sz(a), nb = sz(b); rep(i,na) { vc<pair<frac,int>> d; rep(j,nb) { V x = b[j]-a[i]; d.eb(frac(x.x,x.y), x.side()); } sort(rng(d)); rep(i,sz(d)-1) { if (d[i].fi == d[i+1].fi && d[i].se != d[i+1].se) yes; } } if (k >= 4 && sz(ca) >= 3) { for (V x : cb) { bool ok = true; rep(i,sz(ca)) { if (pline(ca,i).ccw(x) != -1) ok = false; } if (ok) yes; } } swap(a,b); swap(ca,cb); } if (k >= 4) { rep(i,sz(ca))rep(j,sz(cb)) { Line la = pline(ca,i); Line lb = pline(cb,j); if (la.ccw(lb.s) == la.ccw(lb.t)) continue; if (lb.ccw(la.s) == lb.ccw(la.t)) continue; yes; } } no; } }; int main() { // cin.tie(nullptr); ios::sync_with_stdio(false); int ts = 1; // scanf("%d",&ts); rep1(ti,ts) { Solver solver; solver.solve(); } return 0; }