제출 #1308664

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

sir

#include <bits/stdc++.h>
#define pb push_back
#define fr first
#define se second
using namespace std;

typedef long long int ll;
typedef pair<ll, ll> pll;
typedef vector <pll> vpll;
const int maxn=2*1e5+5;

ll ccw(pll a, pll b, pll c) {
	return a.fr * (b.se - c.se) + b.fr * (c.se - a.se) + c.fr * (a.se - b.se);
}

pll ce;
bool half(pll a) {
	if (a.se > ce.se) return 1;
	if (a.se == ce.se && a.fr > ce.fr) return 1;
	return 0; 
}
bool comp(pll a, pll b) {
	if (half(a)!=half(b)) return half(a) > half(b);
	return ccw(a, ce, b) < 0;
}

int m; vpll p;
vpll conv() {
	vpll ans;
	for (int i = 0;i < m;i++) {
		while (ans.size() > 1 && ccw(ans[ans.size()-2], ans[ans.size()-1], p[i]) < 0) ans.pop_back();
		ans.pb(p[i]); 
	}
	return ans;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> n;
	pll s[n]; 
	for (int i=0;i<n;i++) cin >> s[i].fr >> s[i].se;
	cin >> m; p.resize(m);
	for (int i=0;i<m;i++) cin >> p[i].fr >> p[i].se;
	
	vpll c, d;
	sort(p.begin(), p.end()); c=conv(); 
	sort(p.begin(), p.end(), greater<pll>()); d=conv();
	for (int i = 1;i < d.size()-1;i++) c.pb(d[i]);
	
	for (int i = 0;i < c.size();i++) {
		ce.fr+=c[i].fr; ce.se+=c[i].se;
	}
	ce.fr/=c.size(); ce.se/=c.size();
	sort(c.begin(), c.end(), comp);
	
	ll P=0; m=c.size();
	int smeta=0, pt2=2;
	for (int i=0;i<n;i++) {
		while (ccw(c[smeta], s[i], c[(smeta+1)%m]) > 0) smeta=(smeta+1)%m;
		while (ccw(c[smeta], s[i], c[(m+smeta-1)%m]) > 0) smeta=(m+smeta-1)%m;
		ll ans=0;
		while (true) {
			if (ccw(s[i], s[pt2], c[smeta]) > 0) {
				ans+=abs(ccw(s[i], s[(n+pt2-1)%n], s[pt2]));
				pt2=(pt2+1)%n;
			}
			else break;
		}
		
		P=max(ans, P);
	}
	cout << P << endl;
	return 0;
}

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