Submission #248531

#	Time	Username	Problem	Language	Result	Execution time	Memory
248531		vanic	Svjetlost (COI18_svjetlost)	C++14	40 / 100	3086 ms	4864 KiB

Main

#include <iostream>
#include <cstdio>
#include <math.h>
#include <algorithm>
#include <iomanip>

using namespace std;

typedef long long ll;
const int maxn=1e5+5, pot=(1<<17);

int n;
pair < int, int > tock[maxn];
pair < int, int > vektor[maxn];
double val[maxn];
int lij[maxn], des[maxn];

ll ccw(pair < ll, ll > a, pair < ll, ll > b, pair < ll, ll > c){
	return a.first*(b.second-c.second)+b.first*(c.second-a.second)+c.first*(a.second-b.second);
}


double dist(pair < double, double > a, pair < double, double > b){
	return sqrt((a.first-b.first)*(a.first-b.first)+(a.second-b.second)*(a.second-b.second));
}


int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	cout << fixed;
	cout << setprecision(6);
	int a, b;
	for(int i=0; i<n; i++){
		cin >> a >> b;
		tock[i]={a, b};
		lij[i]=(i+n-1)%n;
		des[i]=(i+1)%n;
	}
	for(int i=0; i<n; i++){
		if(i!=n-1){
			vektor[i]={tock[i+1].first-tock[i].first, tock[i+1].second-tock[i].second};
		}
		else{
			vektor[i]={tock[0].first-tock[i].first, tock[0].second-tock[i].second};
		}
	}
	int pos=1;
	double vrij=dist({0, 0}, vektor[0]);
	double maksi=0;
	for(int i=0; i<n; i++){
		while(ccw({0, 0}, vektor[i], vektor[pos])>0){
			vrij+=dist({0, 0}, vektor[pos]);
			pos=(pos+1)%n;
		}
//		cout << val << '\n';
		val[i]=vrij;
		maksi=max(maksi, vrij);
		vrij-=dist({0, 0}, vektor[i]);
	}
	cout << maksi << '\n';
	int q;
	cin >> q;
	int x;
	for(int i=0; i<q; i++){
		cin >> a;
		a--;
		x=lij[a];
		while(ccw({0, 0}, vektor[a], vektor[x])<0){
			val[x]-=dist({0, 0}, vektor[a]);
			x=lij[x];
		}
		x=lij[lij[a]];
		while(ccw({0, 0}, vektor[lij[a]], vektor[x])<0){
			val[x]-=dist({0, 0}, vektor[lij[a]]);
			x=lij[x];
		}
		val[a]=0;
		vektor[lij[a]]={tock[des[a]].first-tock[lij[a]].first, tock[des[a]].second-tock[lij[a]].second};
		vrij=dist({0, 0}, vektor[lij[a]]);
		x=des[a];
		while(ccw({0, 0}, vektor[lij[a]], vektor[x])>0){
			vrij+=dist({0, 0},  vektor[x]);
			x=des[x];
		}
/*		cout << a << " " << x << endl;
		cout << vrij << endl;*/
		x=lij[lij[a]];
		while(ccw({0, 0}, vektor[lij[a]], vektor[x])<0){
			val[x]+=dist({0, 0}, vektor[lij[a]]);
			x=lij[x];
		}
		val[lij[a]]=vrij;
		maksi=0;
		for(int j=0; j<n; j++){
//			cout << val[j] << " ";
			maksi=max(maksi, val[j]);
		}
//		cout << '\n';
		cout << maksi << '\n';
		lij[des[a]]=lij[a];
		des[lij[a]]=des[a];
	}
	return 0;
}

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