제출 #950578

#제출 시각아이디문제언어결과실행 시간메모리
950578berrTriangles (CEOI18_tri)C++17
55 / 100
8 ms748 KiB
#include <bits/stdc++.h> using namespace std; #include <stdio.h> #include <stdlib.h> #include <assert.h> #include "trilib.h" map<array<short, 3>, int> mp; /* 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); }*/ int is_clock(int a, int b, int c){ return is_clockwise(a, b, c); /* if(a<min(b, c)){ if(mp.count({a, b, c})) return mp[{a, b, c}]; else{ int val=is_clockwise(a, b, c); mp[{a, b, c}]=val; mp[{a, c, b}]=!val; return val; } } else if(b<min(a, c)){ return is_clock(b, c, a); } else return is_clock(c, a, b);*/ } 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_clock(1, 2, i)){ if(v==-1) v=i; else if(is_clock(v, 2, i)){ v=i; } } } if(v==-1){ for(int i=3; i<=n; i++){ if(is_clock(2, 1, i)){ if(v==-1) v=i; else if(is_clock(v, 1, i)){ v=i; } } } int u=-1; for(int i=2; i<=n; i++){ if(i==v||i==1) continue; if(is_clock(1, v, i)){ if(u==-1) u=i; else if(is_clock(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_clock(v, u, i)){ if(flag==0) flag=i; else if(is_clock(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_clock(2, v, i)){ if(u==-1) u=i; else if(is_clock(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_clock(v, u, i)){ if(flag==0) flag=i; else if(is_clock(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...