Submission #78951

#TimeUsernameProblemLanguageResultExecution timeMemory
78951aminraTriangles (CEOI18_tri)C++14
0 / 100
3 ms640 KiB
#include <bits/stdc++.h> #include "trilib.h" using namespace std; typedef long long ll; typedef long double ld; const int MOD = (int)1e9 + 7; const int MAXN = (int)107; const int infint = (int)1e9; int n; vector<int> u, d, ans; /*int get_n() { int x; cin >> x; return x; } int is_clockwise(int x, int y, int z) { cout << x << " " << y << " " << z << endl; int ans; cin >> ans; return ans; } void give_answer(int t) { cout << t << endl; return; }*/ bool cw(int i, int j) { return is_clockwise(1, i, j); } bool ccw(int i, int j) { return !is_clockwise(1, i, j); } vector<int> convex(vector<int> v) { vector<int> ans; for (auto u : v) { while(ans.size() >= 2 && is_clockwise(ans[ans.size() - 2], ans.back(), u)) ans.pop_back(); ans.push_back(u); } return ans; } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); n = get_n(); for (int i = 3; i <= n; i++) if(is_clockwise(1, 2, i)) d.push_back(i); else u.push_back(i); sort(d.begin(), d.end(), ccw); sort(u.begin(), u.end(), ccw); d.push_back(2); u.push_back(1); d = convex(d), u = convex(u); for (auto x : d) ans.push_back(x); for (auto x : u) ans.push_back(x); /*for (auto x : ans) cout << x << " "; cout << endl; ans = convex(ans); for (auto x : ans) cout << x << " "; cout << endl;*/ deque<int> qs; for (auto x : ans) qs.push_back(x); bool did = false; while(!did) { did = 1; int a = qs.back(); qs.pop_back(); if(is_clockwise(qs.back(), a, qs.front())) did = 0; else qs.push_back(a); a = qs.front(); qs.pop_front(); if(!is_clockwise(qs.front(), a, qs.back())) did = 0; else qs.push_front(a); } give_answer(qs.size()); }
#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...