Submission #1202910

#TimeUsernameProblemLanguageResultExecution timeMemory
1202910loomTriangles (CEOI18_tri)C++20
100 / 100
14 ms1352 KiB
#include<bits/stdc++.h> #include "trilib.h" using namespace std; #define inf 5e18 #define nl '\n' int P; bool cmp(int a, int b){ return is_clockwise(P, a, b); } deque<int> func(deque<int>& v, int p){ P = p; sort(v.begin(), v.end(), cmp); deque<int> ans; ans.push_back(p); for(int x : v){ while(ans.size() >= 2 and !is_clockwise(ans[ans.size()-2], ans.back(), x)) ans.pop_back(); ans.push_back(x); } return ans; } inline void solve(){ int n = get_n(); deque<int> a, b; for(int i=3; i<=n; i++){ (is_clockwise(1, 2, i) ? b : a).push_back(i); } a = func(a, 1); b = func(b, 2); int x = 1; while(x){ x = 0; while(a.size() >= 2 and b.size() >= 1 and !is_clockwise(b.back(), a[0], a[1])) a.pop_front(), x++; while(a.size() >= 1 and b.size() >= 2 and !is_clockwise(b[b.size()-2], b.back(), a[0])) b.pop_back(), x++; while(a.size() >= 1 and b.size() >= 2 and !is_clockwise(a.back(), b[0], b[1])) b.pop_front(), x++; while(a.size() >= 2 and b.size() >= 1 and !is_clockwise(a[a.size()-2], a.back(), b[0])) a.pop_back(), x++; } give_answer(a.size()+b.size()); } signed main(){ int t = 1; //cin>>t; while(t--) solve(); 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...