제출 #1308614

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1308614		vili	SIR (COI15_sir)	C++20	0 / 100	130 ms	12088 KiB

sir

#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;
	
	//cout<<"BB"<<endl;
	for (int i=0;i<n;i++) {
		pnt2%=n;
		if (i>0 and ccv(v[i],v[(pnt2+1)%n],rj[tr])==1) tr++;
		pnt2%=n;
		tr%=rj.size();
		
		if (i>0) pv-=pvv(v[i],v[pnt2],v[i-1]);
		
		pnt2%=n;
		
		while (ccv(v[i],v[(pnt2+1)%n],rj[tr])==1) {
			pnt2++;
			pnt2%=n;
			pv+=pvv(v[pnt2],v[i],v[(pnt2-1+n)%n]);
			naj=max(naj,pv);
		}	
		//cout <<pnt<<" "<<pnt2<<endl;
	}
	cout << naj;
	
	
	
}

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

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