제출 #932369

#제출 시각아이디문제언어결과실행 시간메모리
932369tminh_hk20SIR (COI15_sir)C++14
0 / 100
119 ms22348 KiB
#include<bits/stdc++.h> #define int long long #define ii pair<int,int> #define fi first #define se second using namespace std; const int N = 6e5; struct vec{ int x, y; }a[N+10], b[N+10]; vec operator - (vec a, vec b){ return {a.x-b.x,a.y-b.y}; } bool operator < (vec a, vec b){ if (a.x==b.x) return a.y<b.y; return a.x<b.x; } int cross(vec a, vec b){ return a.x*b.y-b.x*a.y; } int n, m, c, s[N+10]; vector<vec> v, conv; map<ii,bool> check; void convexhull(){ sort(b+1,b+m+1); //upper v.clear(); v.push_back(b[1]); for (int i=2;i<=m;i++){ while(v.size()>=2 && cross(a[i]-v[v.size()-1],v[v.size()-2]-v[v.size()-1])>0) v.pop_back(); v.push_back(b[i]); } for (vec a: v) check[{a.x,a.y}]=1, conv.push_back(a); // lower v.clear(); v.push_back(b[m]); for (int i=m-1;i>=1;i--){ while(v.size()>=2 && cross(a[i]-v[v.size()-1],v[v.size()-2]-v[v.size()-1])>0) v.pop_back(); v.push_back(b[i]); } for (vec a: v) if (!check[{a.x,a.y}]) conv.push_back(a); } bool ch(int i, int j){ int j2 = (j+1)%c; return cross(conv[j]-a[i],conv[j2]-a[i])<= 0; } int index(int i){ if (i%n==0) return n; else return i%n; } signed main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>> n; for (int i=1;i<=n;i++) cin>> a[i].x>>a[i].y; cin>> m; for (int i=1;i<=m;i++) cin>> b[i].x>>b[i].y; convexhull(); reverse(a+1,a+n+1); for (int i=1;i<=n;i++) a[n+i] =a[i]; for (int i=1;i<=2*n-1;i++) s[i] = s[i-1]+ cross(a[i],a[i+1]); int j =0; c = conv.size(); for (int i=0;i<c;i++){ if (ch(0,i)){ j = i; break; } } // for (int i=1;i<=n;i++) cout <<"bg "<<a[i].x<<" "<<a[i].y<<endl; // for (int i=0;i<c;i++) cout <<"sm "<<conv[i].x<<" "<<conv[i].y<<endl; // for (int i=1;i<=n;i++) cout << s[i]<<" "; cout <<endl; int res = 0; int far = 2; for (int i=1;i<=n;i++){ while(!ch(i,j)){ j++; j%=c; } while(cross(a[far]-a[i],conv[j]-a[i])<0){ int l = i, r = far; if (l>r) swap(l,r); // cout <<i<<" "<<l<<" "<<r<<" "<<s[r-1]-s[l-1]<<" "<<cross(a[r],a[l])<<endl; res = max(res, abs(s[r-1]-s[l-1]+cross(a[r],a[l]))); far++; } // cout <<">"<<i<<" "<<far%n<<endl; } cout <<res<<endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...