| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 163727 |
2019-11-14T20:13:32 Z |
algorithm16 |
SIR (COI15_sir) |
C++14 |
|
827 ms |
6252 KB |
#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
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 time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
376 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
380 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
827 ms |
6252 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
