oj.uz

Submission #248531

# Submission time Handle Problem Language Result Execution time Memory
248531 2020-07-12T15:54:46 Z vanic Svjetlost (COI18_svjetlost) C++14
40 / 100
 3000 ms 4864 KB 
#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.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB 11 numbers
2 Correct 1 ms 384 KB 41 numbers
3 Correct 0 ms 384 KB 11 numbers
4 Correct 1 ms 384 KB 93 numbers

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB 11 numbers
2 Correct 1 ms 384 KB 41 numbers
3 Correct 0 ms 384 KB 11 numbers
4 Correct 1 ms 384 KB 93 numbers
5 Correct 2 ms 384 KB 101 numbers
6 Correct 18 ms 512 KB 1201 numbers
7 Correct 19 ms 512 KB 1556 numbers
8 Correct 23 ms 512 KB 1996 numbers
9 Correct 23 ms 512 KB 1960 numbers
10 Correct 22 ms 512 KB 1991 numbers
11 Correct 24 ms 512 KB 1963 numbers

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB found '32934.3604540000', expected '32934.3604541195', error '0.0000000000'
2 Correct 1 ms 384 KB found '31571636.3365450017', expected '31571636.3365447633', error '0.0000000000'
3 Correct 4 ms 896 KB found '31442617.6286690012', expected '31442617.6286691241', error '0.0000000000'
4 Correct 8 ms 1408 KB found '31424400.0534069985', expected '31424400.0534067489', error '0.0000000000'
5 Correct 29 ms 4864 KB found '3142086769.6889629364', expected '3142086769.6889681816', error '0.0000000000'
6 Correct 29 ms 4856 KB found '3142076120.8714442253', expected '3142076120.8714694977', error '0.0000000000'

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 640 KB 1001 numbers
2 Correct 2114 ms 2104 KB 15001 numbers
3 Execution timed out 3086 ms 3652 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB 11 numbers
2 Correct 1 ms 384 KB 41 numbers
3 Correct 0 ms 384 KB 11 numbers
4 Correct 1 ms 384 KB 93 numbers
5 Correct 2 ms 384 KB 101 numbers
6 Correct 18 ms 512 KB 1201 numbers
7 Correct 19 ms 512 KB 1556 numbers
8 Correct 23 ms 512 KB 1996 numbers
9 Correct 23 ms 512 KB 1960 numbers
10 Correct 22 ms 512 KB 1991 numbers
11 Correct 24 ms 512 KB 1963 numbers
12 Correct 1 ms 384 KB found '32934.3604540000', expected '32934.3604541195', error '0.0000000000'
13 Correct 1 ms 384 KB found '31571636.3365450017', expected '31571636.3365447633', error '0.0000000000'
14 Correct 4 ms 896 KB found '31442617.6286690012', expected '31442617.6286691241', error '0.0000000000'
15 Correct 8 ms 1408 KB found '31424400.0534069985', expected '31424400.0534067489', error '0.0000000000'
16 Correct 29 ms 4864 KB found '3142086769.6889629364', expected '3142086769.6889681816', error '0.0000000000'
17 Correct 29 ms 4856 KB found '3142076120.8714442253', expected '3142076120.8714694977', error '0.0000000000'
18 Correct 22 ms 640 KB 1001 numbers
19 Correct 2114 ms 2104 KB 15001 numbers
20 Execution timed out 3086 ms 3652 KB Time limit exceeded
21 Halted 0 ms 0 KB -