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

提出ソース

結果

問題	No.2173 Nightcord
ユーザー	👑 Nachia
提出日時	2022-12-25 01:07:27
言語	C++17 (gcc 13.2.0 + boost 1.83.0)
結果	AC
実行時間	672 ms / 2,525 ms
コード長	4,602 bytes
コンパイル時間	1,453 ms
コンパイル使用メモリ	96,868 KB
実行使用メモリ	4,384 KB
最終ジャッジ日時	2023-08-11 02:14:36
合計ジャッジ時間	15,172 ms
ジャッジサーバーID （参考情報）	judge12 / judge14

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 4,376 KB
testcase_01	AC	2 ms 4,380 KB
testcase_02	AC	2 ms 4,380 KB
testcase_03	AC	481 ms 4,380 KB
testcase_04	AC	1 ms 4,376 KB
testcase_05	AC	2 ms 4,376 KB
testcase_06	AC	2 ms 4,376 KB
testcase_07	AC	2 ms 4,376 KB
testcase_08	AC	2 ms 4,384 KB
testcase_09	AC	336 ms 4,380 KB
testcase_10	AC	169 ms 4,376 KB
testcase_11	AC	13 ms 4,376 KB
testcase_12	AC	303 ms 4,376 KB
testcase_13	AC	23 ms 4,380 KB
testcase_14	AC	340 ms 4,376 KB
testcase_15	AC	389 ms 4,376 KB
testcase_16	AC	4 ms 4,376 KB
testcase_17	AC	52 ms 4,380 KB
testcase_18	AC	200 ms 4,376 KB
testcase_19	AC	3 ms 4,380 KB
testcase_20	AC	193 ms 4,380 KB
testcase_21	AC	277 ms 4,376 KB
testcase_22	AC	315 ms 4,380 KB
testcase_23	AC	294 ms 4,380 KB
testcase_24	AC	631 ms 4,376 KB
testcase_25	AC	407 ms 4,380 KB
testcase_26	AC	514 ms 4,380 KB
testcase_27	AC	5 ms 4,380 KB
testcase_28	AC	459 ms 4,380 KB
testcase_29	AC	64 ms 4,380 KB
testcase_30	AC	672 ms 4,384 KB
testcase_31	AC	106 ms 4,380 KB
testcase_32	AC	296 ms 4,380 KB
testcase_33	AC	568 ms 4,380 KB
testcase_34	AC	618 ms 4,380 KB
testcase_35	AC	285 ms 4,380 KB
testcase_36	AC	345 ms 4,380 KB
testcase_37	AC	531 ms 4,380 KB
testcase_38	AC	89 ms 4,376 KB
testcase_39	AC	289 ms 4,380 KB
testcase_40	AC	600 ms 4,380 KB
testcase_41	AC	360 ms 4,380 KB
testcase_42	AC	291 ms 4,380 KB
testcase_43	AC	30 ms 4,384 KB
testcase_44	AC	2 ms 4,380 KB
testcase_45	AC	97 ms 4,380 KB
testcase_46	AC	169 ms 4,376 KB
testcase_47	AC	139 ms 4,380 KB
testcase_48	AC	68 ms 4,380 KB
testcase_49	AC	4 ms 4,380 KB
testcase_50	AC	25 ms 4,380 KB
testcase_51	AC	152 ms 4,384 KB
testcase_52	AC	3 ms 4,376 KB
testcase_53	AC	166 ms 4,380 KB
testcase_54	AC	246 ms 4,380 KB
testcase_55	AC	48 ms 4,376 KB
testcase_56	AC	99 ms 4,380 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

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

yukicoder

結果

テストケース

ソースコード