Submission #1308605

#TimeUsernameProblemLanguageResultExecution timeMemory
1308605viliSIR (COI15_sir)C++20
0 / 100
130 ms12088 KiB
#include<bits/stdc++.h>
using namespace std;
 
#define LL long long
#define int LL
#define X first
#define Y second
#define PB push_back
#define INS insert
#define pii pair<int,int>
#define pll pair<LL,LL>

const int N = 3e5+5;
const int INF = 1e9;
const int MOD = 1e9+7;

vector<pii>v;
vector<pii>v2;
vector<pii>rj;
LL ccv(pll a,pll b,pll c) {
	LL odg = a.X*(b.Y-c.Y)+b.X*(c.Y-a.Y)+c.X*(a.Y-b.Y);
	if (odg == 0) return 0;
	return odg/abs(odg);
}
long long pvv(pll a,pll b,pll c) {
	return abs(a.X*(b.Y-c.Y)+b.X*(c.Y-a.Y)+c.X*(a.Y-b.Y));
}
vector<pii> convex() {
	vector<pii>nadi;
	nadi.PB(v2[0]);
	nadi.PB(v2[1]);
	for (int i=2;i<v2.size();i++) {
		while (nadi.size()>1) {
			if (ccv(nadi[nadi.size()-2],nadi.back(),v2[i])<=0) nadi.pop_back();
			else break;
		}
		nadi.PB(v2[i]);
	}
	return nadi;
}
bool cmp(pii a,pii b) {
	LL odg = ccv(v[0],a,b);
	if (odg != 0) return odg > 0;

	LL da = (a.X - v[0].X)*(a.X - v[0].X) + (a.Y - v[0].Y)*(a.Y - v[0].Y);
    LL db = (b.X - v[0].X)*(b.X - v[0].X) + (b.Y - v[0].Y)*(b.Y - v[0].Y);
    return da < db;
}
void solve() {
	int n,a,b;
	cin>>n;
	for (int i=0;i<n;i++) {
		cin>>a>>b;
		v.PB({a,b});
	}
	int m;
	cin>>m;
	for (int i=0;i<m;i++) {
		cin>>a>>b;
		v2.PB({a,b});
	}
	sort(v2.begin(),v2.end());
	if (m>2) {
		
		rj = convex();
		reverse(v2.begin(),v2.end());
		vector<pii> bb = convex();
		for (int i=1;i<bb.size()-1;i++) rj.PB(bb[i]);
	}
	else {
		rj=v2;
	}
	vector<pii>rj2 = rj;	
	int pnt = 0,pnt2=1;
	sort(rj2.begin(),rj2.end(),cmp);
	int tr = 0; 
	for (int i=0;i<rj.size();i++) {
		if (rj[i].X==rj2[0].X and rj[i].Y==rj2[0].Y) {
			tr=i;
			break;
		}
	}
	/*
	cout<<"AA"<<endl;
	for (int i=0;i<rj.size();i++) 	{
		cout<<rj[i].X<<" "<<rj[i].Y<<endl;
	}
	cout<<"BB"<<endl;
	*/
	LL pv = 0;
	LL naj = 0;
	
	while (pnt < n and pnt!=pnt2) {
		pnt2%=n;
		tr%=rj.size();
		int uso = 0;
		while (ccv(v[pnt],v[pnt2],rj[tr])!=1 and pnt < n) {
			uso=1;
			pnt++;
			pnt2%=n;
			pv -= pvv(v[pnt2],v[pnt],v[(pnt-1+n)%n]);
		}
		if (uso==1) {
			tr++;
			tr%=rj.size();
		}
		
			
			
		
		else {
			naj = max(naj,pv);
			//cout << pv <<" "<<pnt<<" "<<pnt2<<" ?? "<<" "<<tr<<endl;
			pnt2++;
			pnt2%=n;
			pv += pvv(v[pnt2],v[pnt],v[(pnt2-1+n)%n]);
		}
		
		
		
	}
	//if (ccv(v[pnt],v[pnt2],rj[tr])==1) naj = max(naj,pv);
	cout << naj;

	
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	solve();
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...