Submission #967252

#	Time	Username	Problem	Language	Result	Execution time	Memory
967252		mdobric	Svjetlost (COI18_svjetlost)	C++11	0 / 100	1 ms	348 KiB

Main

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e5 + 5;
int n, q;
long long a[maxn], b[maxn];
long long max_d = 0, max_poc, max_kraj, max_smjer = 0;

long long calc (int x, int y){
	y = (y + n) % n;
	return abs(a[x] - a[y]) * abs(a[x] - a[y]) + abs(b[x] - b[y]) * abs(b[x] - b[y]);
}

long long ccw (long long a1, long long b1, long long a2, long long b2, long long a3, long long b3){
	return a1 * (b2 - b3) + a2 * (b3 - b1) + a3 * (b1 - b2);
}

int main (void){
	
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> n;
	for (int i = 0; i < n; i++){
		cin >> a[i] >> b[i];
	}
	cin >> q;
	int kraj = 1;
	long long d = calc(0, 1) + calc(1, 2), tx;
	max_poc = 0, max_kraj = 1, max_d = d;
	for (int poc = 0; poc < n; poc++){
		long long a1 = a[poc], b1 = b[poc], a2 = a[(poc + 1) % n], b2 = b[(poc + 1) % n];
		do{
			kraj++;
			kraj = kraj % n;
			long long a3 = a[kraj], b3 = b[kraj], a4 = a[(kraj + 1) % n], b4 = b[(kraj + 1) % n];
			d = d + calc(kraj, kraj + 1);
			tx = ccw(a1, b1, a2, b2, a4 - a3 + a2, b4 - b3 + b2);
		}while(tx > 0);
		d = d - calc(kraj, kraj + 1);
		kraj = kraj + n - 1;
		kraj = kraj % n;
		if (d > max_d){
			max_d = d;
			max_poc = poc;
			max_kraj = kraj;
		}
		//cout << poc << "   " << kraj << endl;
		d = d - calc(poc, poc + 1);
	}
	
	kraj = n - 2;
	d = calc(n - 1, n - 2) + calc(n - 2, n - 3);
	for (int poc = n - 1; poc >= 0; poc--){
		long long a1 = a[poc], b1 = b[poc], a2 = a[(poc - 1 + n) % n], b2 = b[(poc - 1 + n) % n];
		do{
			kraj = kraj + n - 1;
			kraj = kraj % n;
			long long a3 = a[kraj], b3 = b[kraj], a4 = a[(kraj - 1 + n) % n], b4 = b[(kraj - 1 + n) % n];
			d = d + calc(kraj, kraj - 1);
			tx = ccw(a1, b1, a2, b2, a3 - a4 + a2, b3 - b4 + b2);	
		}while(tx > 0);
		d = d - calc(kraj, kraj - 1);
		kraj++;
		kraj = kraj % n;
		if (d > max_d){
			max_d = d;
			max_poc = poc;
			max_kraj = kraj;
			max_smjer = 1;
		}
		d = d - calc(poc, poc - 1);
	}
	double ans_max = 0;
	if (max_smjer == 0){
		int i = max_poc - 1;
		do{
			i++;
			if (i == n){
				i = 0;
			}
			double ans = calc(i, i + 1);
			ans_max += sqrt(ans);			
		}while (i != max_kraj);
	}
	else{
		int i = max_poc + 1;
		do{
			i--;
			if (i == -1){
				i = n - 1;
			}
			double ans = calc(i, i - 1);
			ans_max += sqrt(ans);			
		}while (i != max_kraj);
	}
	cout << fixed;
	cout << setprecision(6);
	cout << ans_max << "\n";
	
	return 0;
}

• Subtask 1: 0 / 12
• Subtask 2: 0 / 14
• Subtask 3: 0 / 14
• Subtask 4: 0 / 29
• Subtask 5: 0 / 31