Submission #164343

#	Time	Username	Problem	Language	Result	Execution time	Memory
164343		algorithm16	SIR (COI15_sir)	C++14	0 / 100	906 ms	6172 KiB

sir

#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;
	if(m==0) {
		cout << -1;
		return 0;
	}
	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";*/
	if(m==1) p2.push_back(p[0]);
	else {
		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 << " " << siz << "\n";
	//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;
			//if(ind2==ind1) break; 
			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";
		if(ind1==ind2) {
			ind2+=1;
			ind2%=n;
		}
		//maxi=max(maxi,pov);
		if(ind1>0) cnt+=1;
	}
	cout << maxi;
	return 0;
}

Compilation message (stderr)

sir.cpp: In function 'int main()':
sir.cpp:89:7: warning: unused variable 'ind12' [-Wunused-variable]
   int ind12=ind1,ind22=ind2,ind32=ind3,b=0;
       ^~~~~
sir.cpp:89:18: warning: unused variable 'ind22' [-Wunused-variable]
   int ind12=ind1,ind22=ind2,ind32=ind3,b=0;
                  ^~~~~
sir.cpp:89:29: warning: unused variable 'ind32' [-Wunused-variable]
   int ind12=ind1,ind22=ind2,ind32=ind3,b=0;
                             ^~~~~

• Subtask 1: 0 / 12
• Subtask 2: 0 / 39
• Subtask 3: 0 / 49