Submission #1308495

#	Time	Username	Problem	Language	Result	Execution time	Memory
1308495		vili	SIR (COI15_sir)	C++20	0 / 100	132 ms	12088 KiB

sir

#include<bits/stdc++.h>
using namespace std;
#define int LL 
#define LL long long
#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 = 2e5;
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])==-1) 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==1) return 1;
	else if (odg==1 and abs(a.X-v[0].X)<=abs(b.X-v[0].X)) return 1;
	else return 0;
}
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());
	rj = convex();
	reverse(v2.begin(),v2.end());
	vector<pii> bb = convex();
	for (int i=1;i<bb.size()-1;i++) rj.PB(bb[i]);
	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;
		}
	}
	LL pv = 0;
	LL naj = 0;
	/*cout<<"A"<<endl;
	for (int i=0;i<rj.size();i++) {
		cout<<rj[i].X<<" "<<rj[i].Y<<endl;
	}
	*/
	//cout << ccv(v[2],v[0],rj[2])<<" ??? !"<<endl;
	//cout << ccv(v[0],v[2],rj[0])<<" ??? !"<<endl;
	while (pnt < n and pnt!=pnt2) {
		pnt2%=n;
		tr%=m;
		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%=m;
		}
		
			
			
		
		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]);
		}
		
		
		
	}
	cout << naj;

	
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	solve();

}
/*
5
0 0
-1 1
1 2
3 1
2 0
1
1 1

*/

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