Submission #480740

#	Time	Username	Problem	Language	Result	Execution time	Memory
480740		wiwiho	Triangles (CEOI18_tri)	C++14	0 / 100	2 ms	204 KiB

tri

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

#define eb emplace_back
#define iter(a) a.begin(), a.end()
#define lsort(a) sort(iter(a))
#define uni(a) a.resize(unique(iter(a)) - a.begin())
#define printv(a, b) {\
    for(auto pv : a) b << pv << " ";\
    b << "\n";\
}

using namespace std;

typedef long long ll;

void waassert(bool b){
    if(b) return;
    cout << "OAO\n";
    exit(0);
}

int n;
vector<int> hull;

int query(int a, int b, int c){
    waassert(a != b && b != c && c != a);
    return is_clockwise(a, b, c);
}

void add(int id){
    //cerr << "test " << id << "\n";
    int m = hull.size();
    bool lst = query(id, hull[m - 1], hull[0]);
    int p = 0;
    int pos = -1;
    for(int i = 0; i < m; i++){
        bool now = query(id, hull[i], hull[(i + 1) % m]);
        //cerr << i << " " << hull[i] << " " << hull[(i + 1) % m] << " " << lst << " " << now << " " << p << "\n";
        if(!(now && lst)) hull[p++] = hull[i];
        if(now && pos == -1) pos = p;
        lst = now;
    }
    //cerr << "ok " << p << " " << pos << " " << id << "\n";
    if(pos != -1) hull.insert(hull.begin() + pos, id), p++;
    hull.resize(p);
    //printv(hull, cerr);
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    n = get_n();
    hull.eb(1);
    hull.eb(2);
    hull.eb(3);
    for(int i = 4; i <= n; i++) add(i);
    give_answer(hull.size());

    return 0;
}

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