Submission #967283

#	Time	Username	Problem	Language	Result	Execution time	Memory
967283		mdobric	Svjetlost (COI18_svjetlost)	C++11	14 / 100	3040 ms	2908 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_poc, max_kraj, max_smjer = 0;
double max_d;
int bio[maxn];
vector <int> dobri;
vector <double> ans;

int v1[maxn], v2[maxn];
 
double calc (int x, int y){
	y = (y + n) % n;
	double prvi = abs(a[x] - a[y]) * abs(a[x] - a[y]), drugi = abs(b[x] - b[y]) * abs(b[x] - b[y]);
	return sqrt(prvi + drugi);
}
 
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 iduci (int tr){
	return v1[tr];
	/*
	tr++;
	tr = tr % n;
	while (bio[tr] == 1){
		tr++;
		tr = tr % n;
	}
	return tr;*/
}
 
int prosli (int tr){
	return v2[tr];
	/*
	tr--;
	tr = (tr + n) % n;
	while (bio[tr] == 1){
		tr--;
		tr = (tr + n) % n;
	}
	return tr;*/
}
 
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];
		v1[i] = (i + 1) % n;
		v2[i] = (i - 1 + n) % n;
	}
	cin >> q;
	int kraj = 1;
	double 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];
		//cout << "d " << d << endl;
		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);
			//cout << "dodaj " << kraj << " " << kraj + 1 << " " << calc(kraj, kraj + 1) << endl;
			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 << " " << d << 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, a4 - a3 + a2, b4 - b3 + 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);
	}
	
	//cout << max_smjer << " " << max_poc << " " << max_kraj << endl;
	ans.push_back(max_d);
	int prvi = 0, zadnji = n - 1;
	for (int i = 0; i < q; i++){
		int makni;
		cin >> makni;
		makni--;
		int gore = iduci(makni), dolje = prosli(makni);
		v1[dolje] = gore;
		v2[gore] = dolje;
		bio[makni] = 1;	
		while (bio[prvi] == 1){
			prvi = iduci(prvi);
		}
		while (bio[zadnji] == 1){
			zadnji = prosli(zadnji);
		}
		d = calc(prvi, iduci(prvi)) + calc(iduci(prvi), iduci(iduci(prvi))), tx;
		kraj = iduci(prvi);
		max_poc = prvi, max_kraj = iduci(prvi), max_d = d;
		for (int poc = prvi; poc < n; poc++){
			if (bio[poc] == 0){
				long long a1 = a[poc], b1 = b[poc], a2 = a[iduci(poc)], b2 = b[iduci(poc)];
				//cout << "d " << d << endl;
				do{
					kraj = iduci(kraj);
					long long a3 = a[kraj], b3 = b[kraj], a4 = a[iduci(kraj)], b4 = b[iduci(kraj)];
					d = d + calc(kraj, iduci(kraj));
					//cout << "dodaj " << kraj << " " << kraj + 1 << " " << calc(kraj, kraj + 1) << endl;
					tx = ccw(a1, b1, a2, b2, a4 - a3 + a1, b4 - b3 + b1);
				}while(tx > 0);
				d = d - calc(kraj, iduci(kraj));
				kraj = prosli(kraj);
				if (d > max_d){
					max_d = d;
					max_poc = poc;
					max_kraj = kraj;
				}
				//cout << poc << "   " << kraj << " " << d << endl;
				d = d - calc(poc, iduci(poc + 1));
			}
			
		}
		
		kraj = prosli(zadnji);
		d = calc(zadnji, prosli(zadnji)) + calc(prosli(zadnji), prosli(prosli(zadnji)));
		//cout << d << endl;
		for (int poc = zadnji; poc >= 0; poc--){
			if (bio[poc] == 0){
				long long a1 = a[poc], b1 = b[poc], a2 = a[prosli(poc)], b2 = b[prosli(poc)];
				do{
					kraj = prosli(kraj);
					long long a3 = a[kraj], b3 = b[kraj], a4 = a[prosli(kraj)], b4 = b[prosli(kraj)];
					d = d + calc(kraj, prosli(kraj));
					tx = ccw(a1, b1, a2, b2, a4 - a3 + a1, b4 - b3 + b1);
					//cout << "? " << poc << " " << kraj << " " << tx << endl;
					//cout << a1 << " " << b1 << "  " << a2 << " " << b2 << "  " << a4 - a3 + a2 << " " << b4 - b3 + b2 << endl;	
				}while(tx < 0);
				d = d - calc(kraj, prosli(kraj));
				kraj = iduci(kraj);
				if (d > max_d){
					max_d = d;
					max_poc = poc;
					max_kraj = kraj;
					max_smjer = 1;
				}
				//cout << poc << " " << kraj << " " << d << endl;
				d = d - calc(poc, prosli(poc));
			}
		}
		ans.push_back(max_d);
	}
	for (int i = 0; i < ans.size(); i++){
		cout << fixed;
		cout << setprecision(6);
		cout << ans[i] << "\n";
	}
	
	return 0;
}

Compilation message (stderr)

svjetlost.cpp: In function 'int main()':
svjetlost.cpp:127:74: warning: right operand of comma operator has no effect [-Wunused-value]
  127 |   d = calc(prvi, iduci(prvi)) + calc(iduci(prvi), iduci(iduci(prvi))), tx;
      |                                                                          ^
svjetlost.cpp:182:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<double>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  182 |  for (int i = 0; i < ans.size(); i++){
      |                  ~~^~~~~~~~~~~~

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