Submission #649575

#TimeUsernameProblemLanguageResultExecution timeMemory
649575ShirleyMPrinted Circuit Board (CEOI12_circuit)C++17
10 / 100
1089 ms3540 KiB
#include <bits/stdc++.h> using namespace std; #define int int64_t typedef vector<int> vi; typedef vector<vi> vvi; typedef pair<int,int> ii; typedef vector<ii> vii; typedef vector<vii> vvii; typedef vector<bool> vb; typedef vector<vb> vvb; #define x first #define y second #define pb push_back #define loop(i,s,e) for(int i=s;i<e;i++) #define loopr(i,s,e) for(int i=e-1; i>=s;i--) #define chkmax(a,b) a=max(a,b) #define chkmin(a,b) a=min(a,b) #define all(a) a.begin(),a.end() #define fast {ios_base::sync_with_stdio(0); cin.tie(0);} const int inf = 1e18; const int INF = 1e9; int n; int mult(int x1, int y1, int x2, int y2, int x3, int y3){ x2-=x1; x3-=x1; y2-=y1; y3-=y1; int ans = (x2*y3 - x3*y2); return ans; } int dir(int x1, int y1, int x2, int y2, int x3, int y3){ int prod = mult(x1,y1,x2,y2,x3,y3); if(prod>0) return 1; else if(prod<0) return -1; return 0; } bool on_line(int x1, int y1, int x2, int y2, int x3, int y3){ bool ans = (min(x1,x2)<=x3 && x3<=max(x1,x2) && min(y1,y2) <= y3 && y3<=max(y1,y2)); return ans; } bool intersection(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4){ int d1 = dir(x1,y1,x2,y2,x4,y4); int d2 = dir(x1,y1,x2,y2,x3,y3); int d3 = dir(x4,y4,x3,y3,x2,y2); int d4 = dir(x4,y4,x3,y3,x1,y1); if(d1*d2<0 && d3*d4<0) return 1; if(!d1 && on_line(x1,y1,x2,y2,x4,y4)) return 1; if(!d2 && on_line(x1,y1,x2,y2,x3,y3)) return 1; if(!d3 && on_line(x3,y3,x4,y4,x2,y2)) return 1; if(!d4 && on_line(x3,y3,x4,y4,x1,y1)) return 1; return 0; } int32_t main() { fast; cin >> n; vii p(n); loop(i,0,n) cin >> p[i].x >> p[i].y; vi good; loop(i,0,n){ bool ok=1; int x1=0, y1=0, x2 = p[i].x, y2 = p[i].y; loop(j,0,n){ int next = (j+1)%n; int x3 = p[j].x, y3 = p[j].y; int x4 = p[next].x, y4 = p[next].y; if(next != i && j != i){ if(!(on_line(x3,y3,x4,y4,x2,y2)&&!dir(x3,y3,x2,y2,x4,y4)) && intersection(x1,y1,x2,y2,x3,y3,x4,y4)){ ok=0; break; } } else{ if(!dir(x3,y3,x4,y4,x1,y1) && on_line(x1,y1,x2,y2,x3,y3) && on_line(x1,y1,x2,y2,x4,y4)){ ok=0; break; } } } if(ok) good.pb(i+1); } sort(all(good)); cout << good.size() << endl; for(int ind:good) cout << ind << " "; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...