Submission #1308666

#	Time	Username	Problem	Language	Result	Execution time	Memory
1308666		vili	SIR (COI15_sir)	C++20	100 / 100	116 ms	29088 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();
	ll ans = 0;
	int smeta=0, pt2=0;
	for (int i=0;i<n;i++) {
		if(i > 0) ans -= abs(ccw(s[i], s[i - 1], s[pt2]));
		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;
		
		while (ccw(s[i], s[(pt2 + 1) % n], c[smeta]) > 0) {
			ans+=abs(ccw(s[i], s[(n+pt2+1)%n], s[pt2]));
			pt2=(pt2+1)%n;
		}
		
		P=max(ans, P);
	}
	cout << P << endl;
	return 0;
}

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