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

提出ソース

結果

問題	No.2173 Nightcord
ユーザー	👑 Nachia
提出日時	2022-12-25 00:52:01
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	RE
実行時間	-
コード長	4,503 bytes
コンパイル時間	1,186 ms
コンパイル使用メモリ	96,888 KB
実行使用メモリ	6,948 KB
最終ジャッジ日時	2024-04-29 06:46:35
合計ジャッジ時間	9,837 ms
ジャッジサーバーID （参考情報）	judge3 / judge4

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	1 ms 5,376 KB
testcase_02	AC	2 ms 5,376 KB
testcase_03	AC	223 ms 5,376 KB
testcase_04	RE	-
testcase_05	RE	-
testcase_06	RE	-
testcase_07	RE	-
testcase_08	RE	-
testcase_09	AC	151 ms 5,376 KB
testcase_10	AC	81 ms 5,376 KB
testcase_11	AC	8 ms 5,376 KB
testcase_12	AC	140 ms 5,376 KB
testcase_13	AC	11 ms 5,376 KB
testcase_14	AC	171 ms 5,376 KB
testcase_15	WA	-
testcase_16	WA	-
testcase_17	AC	24 ms 5,376 KB
testcase_18	AC	91 ms 5,376 KB
testcase_19	AC	2 ms 5,376 KB
testcase_20	AC	86 ms 5,376 KB
testcase_21	AC	130 ms 5,376 KB
testcase_22	AC	145 ms 5,376 KB
testcase_23	AC	134 ms 5,376 KB
testcase_24	AC	284 ms 5,376 KB
testcase_25	AC	178 ms 5,376 KB
testcase_26	AC	242 ms 5,376 KB
testcase_27	AC	3 ms 5,376 KB
testcase_28	AC	210 ms 5,376 KB
testcase_29	AC	29 ms 5,376 KB
testcase_30	AC	297 ms 5,376 KB
testcase_31	AC	48 ms 5,376 KB
testcase_32	WA	-
testcase_33	AC	265 ms 5,376 KB
testcase_34	AC	310 ms 5,376 KB
testcase_35	AC	142 ms 5,376 KB
testcase_36	AC	166 ms 5,376 KB
testcase_37	AC	263 ms 5,376 KB
testcase_38	WA	-
testcase_39	WA	-
testcase_40	AC	300 ms 5,376 KB
testcase_41	AC	182 ms 5,376 KB
testcase_42	WA	-
testcase_43	AC	16 ms 5,376 KB
testcase_44	WA	-
testcase_45	AC	49 ms 5,376 KB
testcase_46	WA	-
testcase_47	AC	72 ms 5,376 KB
testcase_48	WA	-
testcase_49	AC	3 ms 5,376 KB
testcase_50	AC	24 ms 5,376 KB
testcase_51	AC	74 ms 5,376 KB
testcase_52	AC	3 ms 5,376 KB
testcase_53	AC	77 ms 5,376 KB
testcase_54	AC	123 ms 5,376 KB
testcase_55	AC	24 ms 5,376 KB
testcase_56	AC	48 ms 5,376 KB

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

ソースコード

raw source code

#line 1 "Main.cpp"
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <atcoder/modint>
#line 2 "nachia\\geometory\\convex-hull.hpp"


#line 7 "nachia\\geometory\\convex-hull.hpp"

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
#line 8 "Main.cpp"

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 solve1p(vector<Vec2> A, vector<Vec2> B){
    rep(i,A.size()) rep(j,B.size()-1) if(!AupThanB(A[i],B[j],B[j+1])) return true;
    return false;
}

bool solve1(vector<Vec2> A, vector<Vec2> B){
    A = convexHull(A);
    B = convexHull(B);
    return solve1p(A, B) && solve1p(B, A);
}

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.size() > b.size()) swap(a, b);
    bool ansa = solve2(a, b);
    bool ansx = (K>=4) && solve1(a, b);
    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

結果

テストケース

ソースコード