#include #include #include #include #include #include namespace nachia{ template std::vector convexHull(std::vector> points) { int n = points.size(); std::vector ord(n); for(int i=0; i bool { return points[l] < points[r]; }); std::vector res; int ressz = 0; for(int t=0; t<2; t++){ for(int p : ord){ InternalElem x0 = points[p].first, y0 = points[p].second; while(ressz + 2 <= (int)res.size()){ int q = res.back(); InternalElem x1 = points[q].first - x0, y1 = points[q].second - y0; res.pop_back(); InternalElem x2 = points[res.back()].first - x0, y2 = points[res.back()].second - y0; if(x1 * y2 - x2 * y1 > 0) continue; res.push_back(q); break; } res.push_back(p); } if(t == 0) std::reverse(ord.begin(), ord.end()); res.pop_back(); ressz = res.size(); } return res; } } // namespace nachia using namespace std; using i32 = int32_t; using u32 = uint32_t; using i64 = int64_t; using u64 = uint64_t; #define rep(i,n) for(int i=0; i<(int)(n); i++) const i64 INF = 1001001001001001001; using Modint = atcoder::static_modint<998244353>; struct Vec2 { i64 x; i64 y; Vec2 neg() const { return {-x,-y}; } }; Vec2 operator-(Vec2 l, Vec2 r){ return {l.x-r.x,l.y-r.y}; } i64 cross(Vec2 o, Vec2 lh){ return o.x*lh.y-o.y*lh.x; } i64 dot(Vec2 o, Vec2 lh){ return o.x*lh.x+o.y*lh.y; } std::vector sort_points_by_argument(const std::vector& points) { std::vector case_split[9]; for (int i = 0; i < (int)points.size(); i++) { int case_id = 0; if (points[i].x == 0) case_id += 1; if (points[i].x > 0) case_id += 2; if (points[i].y == 0) case_id += 3; if (points[i].y > 0) case_id += 6; case_split[case_id].push_back(i); } auto sort_by_argument_small = [&points](int l, int r)->bool { return points[l].x * points[r].y - points[l].y * points[r].x > 0; }; for (int t = 0; t < 9; t++) { std::sort(case_split[t].begin(), case_split[t].end(), sort_by_argument_small); } std::vector res; res.reserve(points.size()); for (int case_id : { 0, 1, 2, 4, 5, 8, 7, 6, 3 }) { std::copy(case_split[case_id].begin(), case_split[case_id].end(), std::back_inserter(res)); } return res; } vector convexHull(vector A){ vector> P(A.size()); rep(i,A.size()) P[i] = {A[i].x,A[i].y}; auto q = nachia::convexHull(std::move(P)); vector ans; for(int i : q) ans.push_back(A[i]); return ans; } bool AupThanB(Vec2 a, Vec2 b1, Vec2 b2){ if(b1.x > b2.x) swap(b1, b2); if(a.x < b1.x || b2.x < a.x) return true; if(b1.x == b2.x) return a.y > max(b1.y, b2.y); return cross(b2-b1, a-b1) > 0; } bool BupThanA(Vec2 a, Vec2 b1, Vec2 b2){ return AupThanB(a.neg(), b1.neg(), b2.neg()); } bool solve1(vector A, vector B){ A = convexHull(A); B = convexHull(B); A.push_back(A.front()); B.push_back(B.front()); rep(i,A.size()) rep(j,B.size()-1) if(!AupThanB(A[i],B[j],B[j+1])) return false; rep(i,A.size()-1) rep(j,B.size()) if(!BupThanA(B[i],A[j],A[j+1])) return false; return true; } bool solve2(vector A, vector B){ for(Vec2 a : A){ vector Bp(B.size()*2); rep(i,B.size()){ Bp[i*2+0] = a - B[i]; Bp[i*2+1] = B[i] - a; } auto I = sort_points_by_argument(Bp); rep(i,I.size()-1) if(I[i]%2 != I[i+1]%2) if(cross(Bp[I[i]], Bp[I[i+1]]) == 0) if(dot(Bp[I[i]], Bp[I[i+1]]) > 0) return true; } return false; } int main(){ int N; cin >> N; int K; cin >> K; vector a, b; rep(i,N){ int x,y,c; cin >> x >> y >> c; if(c == 1) a.push_back({x,y}); if(c == 2) b.push_back({x,y}); } if(a.empty() || b.empty()){ cout << "No\n"; return 0; } bool ansa = solve2(a, b) || solve2(b, a); bool ansx = (K>=4) && !(solve1(a, b) || solve1(b, a)); if(ansa || ansx) cout << "Yes\n"; else cout << "No\n"; return 0; } struct ios_do_not_sync{ ios_do_not_sync(){ ios::sync_with_stdio(false); cin.tie(nullptr); } } ios_do_not_sync_instance;