Submission #163727

#TimeUsernameProblemLanguageResultExecution timeMemory
163727algorithm16SIR (COI15_sir)C++14
0 / 100
827 ms6252 KiB
#include<iostream> #include<cmath> #include<vector> #include<algorithm> using namespace std; typedef long long int llint; llint n,m,px=1e9,py=1e9,ind,cnt,maxi; vector <pair<int,int> > v; vector <pair<int,int> > p; vector <pair<int,int> > p2; vector <pair<int,int> > p3; double dist(pair <int,int> a,pair <int,int> b) { return sqrt(pow(a.first-b.first,2)+pow(a.second-b.second,2)); } llint ccw(pair <int,int> a,pair <int,int> b,pair <int,int> c) { return c.first*(a.second-b.second)+a.first*(b.second-c.second)+b.first*(c.second-a.second); } bool f(pair <int,int> a,pair <int,int> b) { llint c=px*(a.second-b.second)+a.first*(b.second-py)+b.first*(py-a.second); return (c<0 or (c==0 && dist(make_pair(px,py),a)>dist(make_pair(px,py),b))); } bool f2(pair <int,int> a,pair <int,int> b) { return ccw(v[0],a,b)>0; } int main() { cin >> n; for(int i=0;i<n;i++) { int x,y; cin >> x >> y; v.push_back(make_pair(x,y)); } cin >> m; for(int i=0;i<m;i++) { int x,y; cin >> x >> y; p.push_back(make_pair(x,y)); if(x<px or (x==px && y<py)) { px=x; py=y; ind=i; } } p.erase(p.begin()+ind); sort(p.begin(),p.end(),f); p.push_back(make_pair(px,py)); reverse(p.begin(),p.end()); /*for(int i=0;i<m;i++) { cout << p[i].first << " " << p[i].second << "\n"; } cout << "\n";*/ p2.push_back(p[0]); p2.push_back(p[1]); for(int i=2;i<m;i++) { p2.push_back(p[i]); int ind=p2.size()-1; while(ind>=2 && !(ccw(p2[ind-2],p2[ind-1],p2[ind])>0)) { //cout << p2[ind-1].first << " " << p2[ind-1].second << "\n"; p2.erase(p2.begin()+ind-1); ind-=1; } } p3=p2; sort(p3.begin(),p3.end(),f2); /*for(int i=0;i<p3.size();i++) { cout << p3[i].first << " " << p3[i].second << "\n"; }*/ llint ind1=0,ind2=1,ind3=find(p2.begin(),p2.end(),p3[0])-p2.begin(),pov=0,siz=p2.size(); //cout << ind3 << " " << p2[ind3].first << " " << p2[ind3].second << "\n"; while(true) { if(ind1==0 && cnt>0) break; while(ccw(v[ind2],v[ind1],p2[ind3])<0 && abs(ind2-ind1)>0) { ind2+=1; ind2%=n; pov+=abs(ccw(v[ind1],v[(ind2-1+n)%n],v[ind2])); //cout << pov << "\n" << ccw(v[ind2],v[ind1],p2[ind3]) << "\n"; if(ccw(v[ind2],v[ind1],p2[ind3])<0) maxi=max(maxi,pov); } //cout << ind1 << " " << ind2 << " " << ind3 << " " << pov << " " << maxi << "\n"; int ind12=ind1,ind22=ind2,ind32=ind3,b=0; while(ccw(v[ind2],v[ind1],p2[ind3])>=0 && abs(ind2-ind1)>0) { pov-=abs(ccw(v[ind1],v[(ind1+1)%n],v[ind2])); //cout << pov << "\n"; ind1+=1; ind1%=n; while(ccw(v[ind1],p2[ind3],p2[(ind3+1)%siz])<0) { ind3+=1; ind3%=siz; //cout << ind3 << "\n"; } b+=1; if(ind1==0 && cnt>0) break; } if(ind1==0 && cnt>0) break; maxi=max(maxi,pov); //cout << ind1 << " " << ind2 << " " << ind3 << " " << pov << " " << maxi << "\n\n"; /*while(ccw(v[ind1],p2[ind3],p2[(ind3+1)%p2.size()])<0) { ind3+=1; ind3%=p2.size(); }*/ if(ind1==ind2) ind2+=1; //maxi=max(maxi,pov); if(ind1>0) cnt+=1; } cout << maxi; return 0; }

Compilation message (stderr)

sir.cpp: In function 'int main()':
sir.cpp:80:7: warning: unused variable 'ind12' [-Wunused-variable]
   int ind12=ind1,ind22=ind2,ind32=ind3,b=0;
       ^~~~~
sir.cpp:80:18: warning: unused variable 'ind22' [-Wunused-variable]
   int ind12=ind1,ind22=ind2,ind32=ind3,b=0;
                  ^~~~~
sir.cpp:80:29: warning: unused variable 'ind32' [-Wunused-variable]
   int ind12=ind1,ind22=ind2,ind32=ind3,b=0;
                             ^~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...