結果

問題 No.2173 Nightcord
ユーザー 👑 NachiaNachia
提出日時 2022-12-25 01:07:27
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 675 ms / 2,525 ms
コード長 4,602 bytes
コンパイル時間 1,575 ms
コンパイル使用メモリ 97,220 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-04-28 19:25:26
合計ジャッジ時間 15,569 ms
ジャッジサーバーID
(参考情報)
judge5 / judge2
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 488 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 3 ms
5,376 KB
testcase_06 AC 2 ms
5,376 KB
testcase_07 AC 2 ms
5,376 KB
testcase_08 AC 3 ms
5,376 KB
testcase_09 AC 340 ms
5,376 KB
testcase_10 AC 170 ms
5,376 KB
testcase_11 AC 14 ms
5,376 KB
testcase_12 AC 308 ms
5,376 KB
testcase_13 AC 25 ms
5,376 KB
testcase_14 AC 352 ms
5,376 KB
testcase_15 AC 398 ms
5,376 KB
testcase_16 AC 5 ms
5,376 KB
testcase_17 AC 52 ms
5,376 KB
testcase_18 AC 201 ms
5,376 KB
testcase_19 AC 4 ms
5,376 KB
testcase_20 AC 194 ms
5,376 KB
testcase_21 AC 282 ms
5,376 KB
testcase_22 AC 317 ms
5,376 KB
testcase_23 AC 296 ms
5,376 KB
testcase_24 AC 642 ms
5,376 KB
testcase_25 AC 405 ms
5,376 KB
testcase_26 AC 521 ms
5,376 KB
testcase_27 AC 5 ms
5,376 KB
testcase_28 AC 464 ms
5,376 KB
testcase_29 AC 65 ms
5,376 KB
testcase_30 AC 675 ms
5,376 KB
testcase_31 AC 108 ms
5,376 KB
testcase_32 AC 297 ms
5,376 KB
testcase_33 AC 572 ms
5,376 KB
testcase_34 AC 622 ms
5,376 KB
testcase_35 AC 286 ms
5,376 KB
testcase_36 AC 350 ms
5,376 KB
testcase_37 AC 536 ms
5,376 KB
testcase_38 AC 90 ms
5,376 KB
testcase_39 AC 290 ms
5,376 KB
testcase_40 AC 602 ms
5,376 KB
testcase_41 AC 362 ms
5,376 KB
testcase_42 AC 294 ms
5,376 KB
testcase_43 AC 30 ms
5,376 KB
testcase_44 AC 2 ms
5,376 KB
testcase_45 AC 98 ms
5,376 KB
testcase_46 AC 171 ms
5,376 KB
testcase_47 AC 140 ms
5,376 KB
testcase_48 AC 68 ms
5,376 KB
testcase_49 AC 4 ms
5,376 KB
testcase_50 AC 26 ms
5,376 KB
testcase_51 AC 154 ms
5,376 KB
testcase_52 AC 4 ms
5,376 KB
testcase_53 AC 166 ms
5,376 KB
testcase_54 AC 247 ms
5,376 KB
testcase_55 AC 48 ms
5,376 KB
testcase_56 AC 101 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

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){
    if(A.size() == 1) return 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 BupThanA(Vec2 a, Vec2 b1, Vec2 b2){
    return AupThanB(a.neg(), b1.neg(), b2.neg());
}

bool solve1(vector<Vec2> A, vector<Vec2> 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[j],A[i],A[i+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