Submission #872688

#TimeUsernameProblemLanguageResultExecution timeMemory
872688lovrotTriangles (CEOI18_tri)C++17
0 / 100
1 ms864 KiB
#include <cstdio> #include <vector> #include <stack> #include <vector> #include "trilib.h" #include <algorithm> #define EB emplace_back using namespace std; const int N = 4e4 + 10; vector<int> S[2]; bool ccw(int a, int b, int c) { return is_clockwise(a, b, c); } void output(vector<int> V) { sort(V.begin(), V.end()); for(int x : V) printf("%d ", x); printf("\n"); } void half(vector<int> &V, bool s) { sort(V.begin(), V.end(), [s](int a, int b) { return ccw(1, a, b) == !s; }); vector<int> _V; for(int x : V) { while((int) _V.size() > 1 && ccw(x, end(_V)[-2], end(_V)[-1]) == s) _V.pop_back(); _V.EB(x); } V = _V; } void cut() { int fail = 0; bool s = 0; while(!S[0].empty() && !S[1].empty() && fail < 2) { s ^= 1; if((int) S[s].size() < 2 || ccw(S[!s].back(), end(S[s])[-2], end(S[s])[-1]) == !s) { ++fail; } else { // printf("%d %d %d : %d\n", S[!s].back(), end(S[s])[-2], end(S[s])[-1], ccw(S[!s].back(), end(S[s])[-2], end(S[s])[-1])); fail = 0; S[s].pop_back(); } } } int main() { int n = get_n(); for(int i = 3; i <= n; ++i) S[ccw(1, 2, i)].EB(i); half(S[0], 0); half(S[1], 1); S[0].insert(S[0].begin(), 1); S[1].EB(2); // output(S[0]); // output(S[1]); cut(); reverse(S[0].begin(), S[0].end()); reverse(S[1].begin(), S[1].end()); swap(S[0], S[1]); cut(); printf("%d\n", (int) S[0].size() + (int) S[1].size()); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...