Submission #480743

#	Time	Username	Problem	Language	Result	Execution time	Memory
480743		wiwiho	Triangles (CEOI18_tri)	C++14	0 / 100	1 ms	332 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]);
    vector<bool> del(m);
    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 << "\n";
        if(now && lst) del[i] = true;
        else if(now && pos == -1) pos = i;
        lst = now;
    }
    //printv(del, cerr);
    vector<int> tmp;
    tmp.swap(hull);
    for(int i = 0; i < m; i++){
        if(!del[i]) hull.eb(tmp[i]);
        if(i == pos) hull.eb(id);
    }
    //cerr << "ok  ";
    //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