제출 #1323646

#제출 시각아이디문제언어결과실행 시간메모리
1323646NikoBaoticSIR (COI15_sir)C++20
51 / 100
1095 ms14108 KiB
#include "bits/stdc++.h"

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pii;

#define F first
#define S second
#define	pb push_back
#define	sz(x) ((int)(x).size())
#define all(x) x.begin(), x.end()
#define FIO ios_base::sync_with_stdio(false); cin.tie(0)
#define uid(a, b) uniform_int_distribution<int>(a, b)(rng)

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int N = 3e5 + 10;
const double eps = 1e-9;

int n, m;
pii k[N];
pii p[N];

ll ccw(pii x, pii y, pii z) {
	return x.F * (y.S - z.S) + y.F * (z.S - x.S) + z.F * (x.S - y.S);
}

ll dis(pii x, pii y) {
	return (x.F - y.F) * (x.F - y.F) + (x.S - y.S) * (x.S - y.S);
}

double ok(pii a, pii b) {
	return atan2((a.S - b.S), (a.F - b.F));
}

vector<pii> hull;
vector<pair<double, pii>> nor;

void conv() {
	vector<pii> sor;

	pii mi = p[0];

	for (int i = 0; i < m; i++) {
		mi = min(mi, p[i]);
	}

	sort(p, p + m, [mi](pii a, pii b){
		ll o = ccw(mi, a, b);

		if (o != 0) return o < 0;

		return dis(mi, a) < dis(mi, b);
	});
	

	for (int i = 0; i < m; i++) {
		while (sz(hull) >= 2 and ccw(hull[sz(hull) - 2], hull[sz(hull) - 1], p[i]) >= 0) {
			hull.pop_back();
		}

		hull.pb(p[i]);
	}

	reverse(all(hull));

	int last = sz(hull) - 1;

	for (int i = 0; i < sz(hull); i++) {
		nor.pb({ok(hull[last], hull[i]), {last, i}});

		last = i;
	}

	sort(all(nor));
}

bool check(int a, int b, pii t) {
	return ccw(k[a], k[b], t) > 0;
}

vector<int> ord;

int la = 0;

bool check(int a, int b) {
	double o = ok(k[a], k[b]);

	//int ind = lower_bound(all(nor), make_pair(o, make_pair(0LL, 0LL))) - nor.begin();

	//if (!check(a, b, hull[nor[ind % sz(nor)].S.F])) return 0;
	//if (!check(a, b, hull[nor[ind % sz(nor)].S.S])) return 0;
	if (!check(a, b, hull[nor[0].S.F])) return 0;
	if (!check(a, b, hull[nor[0].S.S])) return 0;
	if (!check(a, b, hull[nor[sz(nor) - 1].S.F])) return 0;
	if (!check(a, b, hull[nor[sz(nor) - 1].S.S])) return 0;

	/*
	ind = nor[ind % sz(nor)].S.F;

	const int K = 10;

	for (int i = ind - K; i < ind + K; i++) {
		if (!check(a, b, hull[(i + sz(hull) * K) % sz(hull)])) return 0;
	}*/

	for (int i = la; i < la + sz(hull); i++) {
		if (!check(a, b, hull[i % sz(hull)])) {
			la = i;
			return 0;
		}
	}

	return 1;
}

int main() {
	FIO;

	cin >> n;

	for (int i = 0; i < n; i++) {
		cin >> k[i].F >> k[i].S;
	}

	cin >> m;

	for (int i = 0; i < m; i++) {
		cin >> p[i].F >> p[i].S;
	}

	conv();

	for (int i = 0; i < sz(hull); i++) {
		ord.pb(i);
	}

	//shuffle(all(ord), rng);

	int ptr = 0;

	ll ans = 0;
	ll po = 0;

	for (int i = 0; i < n; i++) {
		if (ptr <= i) {
			ptr = i + 1;
			po = 0;
		}

		while (1) {
			if (ans < po + abs(ccw(k[i], k[(ptr) % n], k[(ptr + 1) % n])) and !check(i, (ptr + 1) % n)) break;

			po += abs(ccw(k[i], k[(ptr) % n], k[(ptr + 1) % n]));
			ptr++;
		}

		ans = max(ans, po);
		po -= abs(ccw(k[i], k[(i + 1) % n], k[ptr % n]));
	}

	cout << ans << endl;

	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...