Submission #680415

#	Time	Username	Problem	Language	Result	Execution time	Memory
680415		qwerasdfzxcl	Triangles (CEOI18_tri)	C++17	55 / 100	14 ms	980 KiB

tri

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

using namespace std;
typedef long long ll;
int n;

int ccw(int x, int y, int z){
    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=1;i<=n;i++) if (check_hull(i)) build_hull(i);
    printf("FUCK\n");
    return 0;
}

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