Submission #950557

#TimeUsernameProblemLanguageResultExecution timeMemory
950557berrTriangles (CEOI18_tri)C++17
55 / 100
8 ms1032 KiB
#include <bits/stdc++.h> using namespace std; #include <stdio.h> #include <stdlib.h> #include <assert.h> #include "trilib.h" /* static int n; static long long *x, *y; static int queries=0; static void init() { static int is_inited=0; if (is_inited) return; is_inited=1; assert(scanf("%d", &n)==1); x=(long long*)malloc((n+1)*sizeof(long long)); y=(long long*)malloc((n+1)*sizeof(long long)); for (int i=1; i<=n; i++) assert(scanf("%lld%lld", &x[i], &y[i])==2); } int get_n() { init(); return n; } int is_clockwise(int a, int b, int c) { init(); assert(a>=1 && a<=n); assert(b>=1 && b<=n); assert(c>=1 && c<=n); assert(a!=b && a!=c && b!=c); queries++; if(queries == 1000 * 1000 + 1) printf("Too many queries!"); return (x[b]-x[a])*(y[c]-y[a])-(x[c]-x[a])*(y[b]-y[a])<0; } void give_answer(int s) { init(); printf("%d\n", s); }*/ signed main(){ ios_base::sync_with_stdio(false); cin.tie(0); int n=get_n(); int v=-1; for(int i=3; i<=n; i++){ if(is_clockwise(1, 2, i)){ if(v==-1) v=i; else if(is_clockwise(v, 2, i)){ v=i; } } } if(v==-1){ for(int i=3; i<=n; i++){ if(is_clockwise(2, 1, i)){ if(v==-1) v=i; else if(is_clockwise(v, 1, i)){ v=i; } } } int u=-1; for(int i=2; i<=n; i++){ if(i==v||i==1) continue; if(is_clockwise(1, v, i)){ if(u==-1) u=i; else if(is_clockwise(u, v, i)){ u=i; } } } vector<int> vis(n+1); vis[u]=1; vis[v]=1; int flag=1; vector<int> ans; ans.push_back(v); ans.push_back(u); while(flag){ flag=0; for(int i=1; i<=n; i++){ if(i==u || i==v) continue; if(is_clockwise(v, u, i)){ if(flag==0) flag=i; else if(is_clockwise(flag, u, i)){ flag = i; } } } ans.push_back(flag); if(vis[flag]||flag==0) break; vis[flag] = 1; v=u; u=flag; } reverse(ans.begin(), ans.end()); while(ans.back()!=ans[0]) ans.pop_back(); give_answer(ans.size()-1);; } else{ int u=-1; for(int i=1; i<=n; i++){ if(i==v||i==2) continue; if(is_clockwise(2, v, i)){ if(u==-1) u=i; else if(is_clockwise(u, v, i)){ u=i; } } } assert(u!=-1); vector<int> vis(n+1); vis[u]=1; vis[v]=1; int flag=1; vector<int> ans; ans.push_back(v); ans.push_back(u); while(flag){ flag=0; for(int i=1; i<=n; i++){ if(i==u || i==v) continue; if(is_clockwise(v, u, i)){ if(flag==0) flag=i; else if(is_clockwise(flag, u, i)){ flag = i; } } } ans.push_back(flag); if(vis[flag]||flag==0) break; vis[flag] = 1; v=u; u=flag; } reverse(ans.begin(), ans.end()); while(ans.back()!=ans[0]) ans.pop_back(); //Afor(auto i: ans) cout<<i<<" "; give_answer(ans.size()-1);; } }
#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...