結果

問題 No.2173 Nightcord
コンテスト
ユーザー Nachia
提出日時 2022-12-25 00:59:42
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 4,364 bytes
コンパイル時間 4,674 ms
コンパイル使用メモリ 134,408 KB
最終ジャッジ日時 2025-02-09 20:31:02
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 52 WA * 2
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <atcoder/modint>

namespace nachia{

template<class Elem, class InternalElem = Elem>
std::vector<int> convexHull(std::vector<std::pair<Elem, Elem>> points) {
    int n = points.size();
    std::vector<int> ord(n);
    for(int i=0; i<n; i++) ord[i] = i;
    std::sort(ord.begin(), ord.end(), [&](int l, int r) -> bool { return points[l] < points[r]; });
    std::vector<int> 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<int> sort_points_by_argument(const std::vector<Vec2>& points) {
    std::vector<int> 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<int> 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<Vec2> convexHull(vector<Vec2> A){
    vector<pair<i64, i64>> P(A.size());
    rep(i,A.size()) P[i] = {A[i].x,A[i].y};
    auto q = nachia::convexHull(std::move(P));
    vector<Vec2> 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 solve1(vector<Vec2> A, vector<Vec2> B){
    A = convexHull(A);
    B = convexHull(B);
    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;
    return true;
}

bool solve2(vector<Vec2> A, vector<Vec2> B){
    for(Vec2 a : A){
        vector<Vec2> 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<Vec2> 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;
0