Submission #1325195

#TimeUsernameProblemLanguageResultExecution timeMemory
1325195Ivo_12SIR (COI15_sir)C++20
0 / 100
1095 ms332 KiB
#include <bits/stdc++.h>
#define ll long long
#define mp make_pair
#define F first
#define S second
#define pii pair < int, int >
#define pb push_back
#define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

using namespace std;

const int N = 3e3+10;

pii poly[N];
int n, m;
pii nodes[N];

int ccw( pair < ll, ll > a,  pair < ll, ll > b,  pair < ll, ll > c ) {
	ll temp = a.F * (b.S - c.S) + b.F * (c.S - a.S) + c.F * (a.S - b.S);
	if(temp > 0) return 1;
	if(temp < 0) return -1;
	return 0;
}

ll find_max( int x ) {
	
	int out = 0;
	for(int i = 2; i < n; i++) {
		for(int j = 0; j < m; j++) {
			if(ccw(poly[x], poly[(x + i) % n], nodes[j]) != 1) {
				return out;
			}
		}
		
		out += abs(poly[x].F * (poly[(x + i - 1) % n].S - poly[(x + i) % n].S) + poly[(x + i - 1) % n].F * (poly[(x + i) % n].S - poly[x].S)
		 + poly[(x + i) % n].F * (poly[x].S - poly[(x + i - 1) % n].S));
	}
	
	return out;
}

void task( void ) {
	
	cin >> n;
	for(int i = 0; i < n; i++) cin >> poly[i].F >> poly[i].S;
	
	cin >> m;
	for(int i = 0; i < m; i++) cin >> nodes[i].F >> nodes[i].S;
	
	ll sol = 0;
	for(int i = 0; i < n; i++) sol = max(sol, find_max(i));
	
	cout << sol << "\n";
	
	return;
}

int main( void ) {
	
	FIO;
	ll tt = 1;
	while(tt--) task();
	
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...