#828328 (C++17) No.2173 Nightcord

• 問題: No.2173 Nightcord
• ユーザー: snuke
• 提出日時: 2022-12-25 07:16:47
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 1,370 ms / 2,525 ms
• コード長: 8,513 bytes
• コンパイル時間: 2,627 ms
• コンパイル使用メモリ: 223,472 KB
• 実行使用メモリ: 5,248 KB
• 最終ジャッジ日時: 2024-11-17 14:32:38
• 合計ジャッジ時間: 24,061 ms
• ジャッジサーバーID （参考情報）: judge2 / judge5

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 5,248 KB
testcase_01	AC	2 ms; 5,248 KB
testcase_02	AC	2 ms; 5,248 KB
testcase_03	AC	1,047 ms; 5,248 KB
testcase_04	AC	2 ms; 5,248 KB
testcase_05	AC	3 ms; 5,248 KB
testcase_06	AC	2 ms; 5,248 KB
testcase_07	AC	2 ms; 5,248 KB
testcase_08	AC	3 ms; 5,248 KB
testcase_09	AC	762 ms; 5,248 KB
testcase_10	AC	200 ms; 5,248 KB
testcase_11	AC	35 ms; 5,248 KB
testcase_12	AC	344 ms; 5,248 KB
testcase_13	AC	63 ms; 5,248 KB
testcase_14	AC	920 ms; 5,248 KB
testcase_15	AC	853 ms; 5,248 KB
testcase_16	AC	4 ms; 5,248 KB
testcase_17	AC	134 ms; 5,248 KB
testcase_18	AC	234 ms; 5,248 KB
testcase_19	AC	7 ms; 5,248 KB
testcase_20	AC	229 ms; 5,248 KB
testcase_21	AC	638 ms; 5,248 KB
testcase_22	AC	718 ms; 5,248 KB
testcase_23	AC	335 ms; 5,248 KB
testcase_24	AC	1,370 ms; 5,248 KB
testcase_25	AC	447 ms; 5,248 KB
testcase_26	AC	1,121 ms; 5,248 KB
testcase_27	AC	11 ms; 5,248 KB
testcase_28	AC	501 ms; 5,248 KB
testcase_29	AC	165 ms; 5,248 KB
testcase_30	AC	713 ms; 5,248 KB
testcase_31	AC	260 ms; 5,248 KB
testcase_32	AC	473 ms; 5,248 KB
testcase_33	AC	829 ms; 5,248 KB
testcase_34	AC	891 ms; 5,248 KB
testcase_35	AC	438 ms; 5,248 KB
testcase_36	AC	525 ms; 5,248 KB
testcase_37	AC	783 ms; 5,248 KB
testcase_38	AC	129 ms; 5,248 KB
testcase_39	AC	416 ms; 5,248 KB
testcase_40	AC	911 ms; 5,248 KB
testcase_41	AC	542 ms; 5,248 KB
testcase_42	AC	615 ms; 5,248 KB
testcase_43	AC	78 ms; 5,248 KB
testcase_44	AC	2 ms; 5,248 KB
testcase_45	AC	247 ms; 5,248 KB
testcase_46	AC	360 ms; 5,248 KB
testcase_47	AC	332 ms; 5,248 KB
testcase_48	AC	157 ms; 5,248 KB
testcase_49	AC	10 ms; 5,248 KB
testcase_50	AC	61 ms; 5,248 KB
testcase_51	AC	363 ms; 5,248 KB
testcase_52	AC	6 ms; 5,248 KB
testcase_53	AC	391 ms; 5,248 KB
testcase_54	AC	562 ms; 5,248 KB
testcase_55	AC	124 ms; 5,248 KB
testcase_56	AC	246 ms; 5,248 KB

ソースコード

#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;
}