제출 #468145

#제출 시각아이디문제언어결과실행 시간메모리
468145ivan_tudorTriangles (CEOI18_tri)C++14
0 / 100
1 ms332 KiB
#include<bits/stdc++.h> #include"trilib.h" using namespace std; int root; bool cmp(int x, int y){ return is_clockwise(root, x, y); } vector<int> getstv(vector<int> v, int st, int en){ root = st; sort(v.begin(), v.end(), cmp); vector<int> stv; stv.push_back(st); for(auto x: v){ while(stv.size() > 1 && is_clockwise(stv.end()[-2], stv.end()[-1], x) == false) stv.pop_back(); stv.push_back(x); } return stv; } int main(){ int n = get_n(); int a = 3; int b = 6; vector<int> l, r; for(int i = 1; i<= n; i++){ if(i == a) continue; if(i == b) continue; if(is_clockwise(a, b, i) == false) l.push_back(i); else r.push_back(i); } ///L ARE ORDINEA DE LA A LA B, R DE LA B LA A vector<int> stvl = getstv(l, a, b); vector<int> stvr = getstv(r, b, a); if(l.size() == 0){ int x = a; while(stvr.size() > 1 && is_clockwise(stvr.end()[-2], stvr.end()[-1], x) == false) stvr.pop_back(); stvr.push_back(x); give_answer(stvr.size()); return 0 ; } if(r.size() == 0){ int x = b; while(stvl.size() > 1 && is_clockwise(stvl.end()[-2], stvl.end()[-1], x) == false) stvl.pop_back(); stvl.push_back(x); give_answer(stvl.size()); return 0 ; } vector<int> stv = stvl; for(auto x: stvr){ while(stv.size() > 1 && (is_clockwise(stv.end()[-2], stv.end()[-1], x) == false)) stv.pop_back(); stv.push_back(x); } for(auto x: stvl){ while(stv.size() > 1 && (is_clockwise(stv.end()[-2], stv.end()[-1], x) == false)) stv.pop_back(); stv.push_back(x); } vector<int> lap(n + 1, -1); int ans =INT_MAX; int pz = 0; for(auto x: stv){ if(lap[x] != -1) ans = min(ans, pz - lap[x]); lap[x] = pz; pz++; } give_answer(ans); }
#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...