Submission #680417

#	Time	Username	Problem	Language	Result	Execution time	Memory
680417		qwerasdfzxcl	Triangles (CEOI18_tri)	C++17	75 / 100	23 ms	2540 KiB

tri

#include "trilib.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
constexpr int ITER = 3;
int n, cnt[100100], qcnt;

int ccw(int x, int y, int z){
    qcnt++;
    assert(qcnt <= 1000000);
    return is_clockwise(x, y, z)?-1:1;
}

bool check_hull(int s){
    int L, R;
    L = R = (s==1)?2:1;

    for (int i=1;i<=n;i++) if (i!=s && i!=L){
        if (ccw(s, L, i)==1) L = i;
        else if (ccw(s, R, i)==-1) R = i;

        //printf("%d: L = %d R = %d\n", s, L, R);

        if (ccw(s, L, R)==1) return 0;
    }
    return 1;
}

int O;
bool cmp(int x, int y){
    return ccw(O, x, y)==1;
}

void build_hull(int s){
    O = s;
    vector<int> P, hull;
    for (int i=1;i<=n;i++) if (i!=s) P.push_back(i);
    sort(P.begin(), P.end(), cmp);

    hull.push_back(s);
    for (auto &x:P){
        while(hull.size()>=2 && ccw(*++hull.rbegin(), hull.back(), x)==-1) hull.pop_back();
        hull.push_back(x);
    }
    give_answer(hull.size());
    exit(0);
}

int main(){
    n = get_n();
    for (int i=3;i<=3;i++) if (check_hull(i)) build_hull(i);
    O = 3;

    vector<int> upper, lower;
    upper.push_back(1);
    for (int i=2;i<=n;i++) if (i!=O){
        if (ccw(O, 1, i) > 0) upper.push_back(i);
        else lower.push_back(i);
    }

    sort(upper.begin(), upper.end(), cmp);
    sort(lower.begin(), lower.end(), cmp);

    vector<int> P = upper, hull;
    for (auto &x:lower) P.push_back(x);

    for (int z=0;z<ITER;z++){
        for (auto &x:P){
            while(hull.size()>=2 && ccw(*++hull.rbegin(), hull.back(), x)==-1) hull.pop_back();
            hull.push_back(x);
        }
    }
    for (auto &x:hull) cnt[x]++;

    int ans = 0;
    for (int i=1;i<=n;i++) if (cnt[i]==ITER) ans++;
    give_answer(ans);
    return 0;
}

• Subtask 1: 15 / 15
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 0 / 25