#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];
int lij[maxn], des[maxn];
struct tournament{
double t[pot*2];
double prop[pot*2];
void propagate(int x){
t[x]+=prop[x];
if(x<pot){
prop[x*2]+=prop[x];
prop[x*2+1]+=prop[x];
}
prop[x]=0;
}
void update(int x, double val){
t[x]+=val;
for(x/=2; x>0; x/=2){
propagate(x*2);
propagate(x*2+1);
t[x]=max(t[x*2], t[x*2+1]);
}
}
void update1(int L, int D, int x, int l, int d, double val){
propagate(x);
if(L>=l && D<=d){
// cout << "updateam " << x << endl;
update(x, val);
if(x<pot){
prop[x*2]+=val;
prop[x*2+1]+=val;
}
return;
}
if((L+D)/2>=l){
update1(L, (L+D)/2, x*2, l, d, val);
}
if((L+D)/2+1<=d){
update1((L+D)/2+1, D, x*2+1, l, d, val);
}
}
double query(int L, int D, int x, int l, int d){
propagate(x);
if(L>=l && D<=d){
return t[x];
}
double lijeva=0, desna=0;
if((L+D)/2>=l){
lijeva=query(L, (L+D)/2, x*2, l, d);
}
if((L+D)/2+1<=d){
desna=query((L+D)/2+1, D, x*2+1, l, d);
}
return max(lijeva, desna);
}
void cisti(int L, int D, int x, int l, int d){
propagate(x);
if(L>=l && D<=d){
return;
}
if((L+D)/2>=l){
cisti(L, (L+D)/2, x*2, l, d);
}
if((L+D)/2+1<=d){
cisti((L+D)/2+1, D, x*2+1, l, d);
}
}
};
struct tournament1{
double t[pot*2];
void update(int x, double val){
t[x]=val;
for(x/=2; x>0; x/=2){
t[x]=t[x*2]+t[x*2+1];
}
}
double query(int L, int D, int x, int l, int d){
if(L>=l && D<=d){
return t[x];
}
double lijeva=0, desna=0;
if((L+D)/2>=l){
lijeva=query(L, (L+D)/2, x*2, l, d);
}
if((L+D)/2+1<=d){
desna=query((L+D)/2+1, D, x*2+1, l, d);
}
return lijeva+desna;
}
};
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));
}
struct tournament2{
pair < int, int > t[pot*2];
pair < int, int > prop[pot*2];
pair < int, int > prazno={1e9+1, 1e9+1};
tournament2(){
for(int i=0; i<pot*2; i++){
prop[i]=prazno;
}
}
void propagate(int x){
if(prop[x]!=prazno){
t[x]=prop[x];
if(x<pot){
prop[x*2]=prop[x];
prop[x*2+1]=prop[x];
}
prop[x]=prazno;
}
}
void update(int x, pair < int, int > val){
t[x]=val;
for(x/=2; x>0; x/=2){
propagate(x*2+1);
t[x]=t[x*2+1];
}
}
void update1(int L, int D, int x, int l, int d, pair < int, int > val){
propagate(x);
if(L>=l && D<=d){
update(x, val);
if(x<pot){
prop[x*2]=val;
prop[x*2+1]=val;
}
return;
}
if((L+D)/2>=l){
update1(L, (L+D)/2, x*2, l, d, val);
}
if((L+D)/2+1<=d){
update1((L+D)/2+1, D, x*2+1, l, d, val);
}
}
int query(int L, int D, int x, int l, int d, pair < int, int > val){
propagate(x);
int y;
if(L>=l && D<=d){
if(ccw({0, 0}, val, t[x])>0){
return -1;
}
if(val==t[x]){
return -1;
}
if(x>=pot){
return x-pot;
}
propagate(x*2);
if(ccw({0, 0}, val, t[x*2])>0 || t[x*2]==val){
return query((L+D)/2+1, D, x*2+1, l, d, val);
}
else{
return query(L, (L+D)/2, x*2, l, d, val);
}
}
if((L+D)/2>=l){
y=query(L, (L+D)/2, x*2, l, d, val);
if(y!=-1){
return y;
}
}
if((L+D)/2+1<=d){
return query((L+D)/2+1, D, x*2+1, l, d, val);
}
return -1;
}
};
tournament T;
tournament1 T1;
tournament2 T2;
int binary(int pos){
int lo=0, hi=n, mid;
while(lo<hi){
mid=(lo+hi)/2+1;
if(ccw({0, 0}, vektor[pos], vektor[(pos+mid)%n])>0){
lo=mid;
}
else{
hi=mid-1;
}
}
return lo;
}
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};
T1.update(i+pot, dist(tock[i], tock[i+1]));
}
else{
vektor[i]={tock[0].first-tock[i].first, tock[0].second-tock[i].second};
T1.update(i+pot, dist(tock[i], tock[0]));
}
T2.update(i+pot, vektor[i]);
}
int pos=1;
double val=dist({0, 0}, vektor[0]);
for(int i=0; i<n; i++){
while(ccw({0, 0}, vektor[i], vektor[pos])>0){
val+=dist({0, 0}, vektor[pos]);
pos=(pos+1)%n;
}
// cout << val << '\n';
T.update(pot+i, val);
val-=dist({0, 0}, vektor[i]);
}
cout << T.query(0, pot-1, 1, 0, n-1) << '\n';
int q;
cin >> q;
int x;
for(int i=0; i<q; i++){
cin >> a;
a--;
// x=(binary(a)+a)%n;
x=T2.query(0, pot-1, 1, a, n-1, vektor[a]);
if(x==-1){
x=T2.query(0, pot-1, 1, 0, a-1, vektor[a]);
}
if(ccw({0, 0}, vektor[a], vektor[x])==0){
x=des[x];
}
// cout << a << " " << x << endl;
if(x>a){
T.update1(0, pot-1, 1, x, n-1, -dist({0, 0}, vektor[a]));
T.update1(0, pot-1, 1, 0, a, -dist({0, 0}, vektor[a]));
}
else{
T.update1(0, pot-1, 1, x, a, -dist({0, 0}, vektor[a]));
}
/* T.cisti(0, pot-1, 1, x, x);
cout << T.t[x+pot] << endl;*/
x=T2.query(0, pot-1, 1, lij[a], n-1, vektor[lij[a]]);
if(x==-1){
x=T2.query(0, pot-1, 1, 0, lij[a]-1, vektor[lij[a]]);
}
// cout << x << endl;
// x=(binary(lij[a])+lij[a])%n;
if(ccw({0, 0}, vektor[lij[a]], vektor[x])==0){
x=des[x];
}
// cout << lij[a] << " " << x << endl;
/* cout << vektor[lij[a]].first << " " << vektor[lij[a]].second << '\n';
cout << vektor[x].first << " " << vektor[x].second << '\n';*/
// cout << "kraj\n";
if(x>lij[a]){
T.update1(0, pot-1, 1, x, n-1, -dist({0, 0}, vektor[lij[a]]));
T.update1(0, pot-1, 1, 0, lij[a], -dist({0, 0}, vektor[lij[a]]));
}
else{
T.update1(0, pot-1, 1, x, lij[a], -dist({0, 0}, vektor[lij[a]]));
}
/*
cout << dist({0, 0}, vektor[lij[a]]) << endl;
T.cisti(0, pot-1, 1, x, x);
cout << T.t[x+pot] << endl;
*/
vektor[lij[a]]={tock[des[a]].first-tock[lij[a]].first, tock[des[a]].second-tock[lij[a]].second};
// cout << "range " << lij[a] << " " << (des[a]+n-1)%n << endl;
if(lij[a]<(des[a]+n-1)%n){
T2.update1(0, pot-1, 1, lij[a], (des[a]+n-1)%n, vektor[lij[a]]);
}
else{
T2.update1(0, pot-1, 1, lij[a], n-1, vektor[lij[a]]);
T2.update1(0, pot-1, 1, 0, (des[a]+n-1)%n, vektor[lij[a]]);
}
T1.update(lij[a]+pot, dist(tock[des[a]], tock[lij[a]]));
T1.update(a+pot, 0);
T.cisti(0, pot-1, 1, lij[a], lij[a]);
T.cisti(0, pot-1, 1, a, a);
T.update(a+pot, -T.t[a+pot]);
T.update(a+pot, -1e9);
T.update(lij[a]+pot, -T.t[lij[a]+pot]);
lij[des[a]]=lij[a];
des[lij[a]]=des[a];
x=T2.query(0, pot-1, 1, lij[a], n-1, vektor[lij[a]]);
// cout << lij[a] << " " << x << endl;
if(x==-1){
x=T2.query(0, pot-1, 1, 0, lij[a]-1, vektor[lij[a]]);
}
x=lij[x];
// x=(binary(lij[a])+lij[a])%n;
// cout << lij[a] << " " << x << endl;
// cout << vektor[lij[a]].first << " " << vektor[lij[a]].second << '\n';
if(x>lij[a]){
T.update(lij[a]+pot, T1.query(0, pot-1, 1, lij[a], x));
/* cout << "tu" << endl;
cout << T1.query(0, pot-1, 1, lij[a], x) << '\n';*/
}
else{
T.update(lij[a]+pot, T1.query(0, pot-1, 1, lij[a], n-1)+T1.query(0, pot-1, 1, 0, x));
/* cout << "ovdje" << endl;
cout << T1.query(0, pot-1, 1, lij[a], n-1)+T1.query(0, pot-1, 1, 0, x) << '\n';*/
}
if(ccw({0, 0}, vektor[lij[a]], vektor[des[x]])==0){
x=des[x];
}
x=des[x];
// cout << T.query(0, pot-1, 1, 0, n-1) << '\n';
// cout << lij[a] << " " << x << endl;
/*
T.cisti(0, pot-1, 1, x, x);
cout << T.t[x+pot] << endl;*/
if(x>lij[a]){
T.update1(0, pot-1, 1, x, n-1, dist({0, 0}, vektor[lij[a]]));
if(lij[a]){
T.update1(0, pot-1, 1, 0, lij[a]-1, dist({0, 0}, vektor[lij[a]]));
}
}
else{
T.update1(0, pot-1, 1, x, lij[a]-1, dist({0, 0}, vektor[lij[a]]));
}
cout << T.query(0, pot-1, 1, 0, n-1) << '\n';
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4608 KB |
11 numbers |
| 2 |
Correct |
3 ms |
4608 KB |
41 numbers |
| 3 |
Correct |
3 ms |
4608 KB |
11 numbers |
| 4 |
Correct |
4 ms |
4608 KB |
93 numbers |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4608 KB |
11 numbers |
| 2 |
Correct |
3 ms |
4608 KB |
41 numbers |
| 3 |
Correct |
3 ms |
4608 KB |
11 numbers |
| 4 |
Correct |
4 ms |
4608 KB |
93 numbers |
| 5 |
Correct |
4 ms |
4736 KB |
101 numbers |
| 6 |
Correct |
16 ms |
4736 KB |
1201 numbers |
| 7 |
Correct |
18 ms |
4876 KB |
1556 numbers |
| 8 |
Correct |
27 ms |
4864 KB |
1996 numbers |
| 9 |
Correct |
24 ms |
4864 KB |
1960 numbers |
| 10 |
Correct |
26 ms |
4864 KB |
1991 numbers |
| 11 |
Correct |
25 ms |
4864 KB |
1963 numbers |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4608 KB |
found '32934.3604540000', expected '32934.3604541195', error '0.0000000000' |
| 2 |
Correct |
4 ms |
4736 KB |
found '31571636.3365450017', expected '31571636.3365447633', error '0.0000000000' |
| 3 |
Correct |
9 ms |
5632 KB |
found '31442617.6286690012', expected '31442617.6286691241', error '0.0000000000' |
| 4 |
Correct |
15 ms |
6400 KB |
found '31424400.0534069985', expected '31424400.0534067489', error '0.0000000000' |
| 5 |
Correct |
58 ms |
10872 KB |
found '3142086769.6889629364', expected '3142086769.6889681816', error '0.0000000000' |
| 6 |
Correct |
62 ms |
10872 KB |
found '3142076120.8714442253', expected '3142076120.8714694977', error '0.0000000000' |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
4864 KB |
1001 numbers |
| 2 |
Correct |
175 ms |
7160 KB |
15001 numbers |
| 3 |
Correct |
522 ms |
10360 KB |
44445 numbers |
| 4 |
Correct |
323 ms |
12664 KB |
22223 numbers |
| 5 |
Correct |
1022 ms |
15480 KB |
88889 numbers |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4608 KB |
11 numbers |
| 2 |
Correct |
3 ms |
4608 KB |
41 numbers |
| 3 |
Correct |
3 ms |
4608 KB |
11 numbers |
| 4 |
Correct |
4 ms |
4608 KB |
93 numbers |
| 5 |
Correct |
4 ms |
4736 KB |
101 numbers |
| 6 |
Correct |
16 ms |
4736 KB |
1201 numbers |
| 7 |
Correct |
18 ms |
4876 KB |
1556 numbers |
| 8 |
Correct |
27 ms |
4864 KB |
1996 numbers |
| 9 |
Correct |
24 ms |
4864 KB |
1960 numbers |
| 10 |
Correct |
26 ms |
4864 KB |
1991 numbers |
| 11 |
Correct |
25 ms |
4864 KB |
1963 numbers |
| 12 |
Correct |
3 ms |
4608 KB |
found '32934.3604540000', expected '32934.3604541195', error '0.0000000000' |
| 13 |
Correct |
4 ms |
4736 KB |
found '31571636.3365450017', expected '31571636.3365447633', error '0.0000000000' |
| 14 |
Correct |
9 ms |
5632 KB |
found '31442617.6286690012', expected '31442617.6286691241', error '0.0000000000' |
| 15 |
Correct |
15 ms |
6400 KB |
found '31424400.0534069985', expected '31424400.0534067489', error '0.0000000000' |
| 16 |
Correct |
58 ms |
10872 KB |
found '3142086769.6889629364', expected '3142086769.6889681816', error '0.0000000000' |
| 17 |
Correct |
62 ms |
10872 KB |
found '3142076120.8714442253', expected '3142076120.8714694977', error '0.0000000000' |
| 18 |
Correct |
14 ms |
4864 KB |
1001 numbers |
| 19 |
Correct |
175 ms |
7160 KB |
15001 numbers |
| 20 |
Correct |
522 ms |
10360 KB |
44445 numbers |
| 21 |
Correct |
323 ms |
12664 KB |
22223 numbers |
| 22 |
Correct |
1022 ms |
15480 KB |
88889 numbers |
| 23 |
Correct |
1372 ms |
15992 KB |
98175 numbers |
| 24 |
Correct |
324 ms |
7544 KB |
25905 numbers |
| 25 |
Correct |
1246 ms |
16120 KB |
98169 numbers |
| 26 |
Correct |
1169 ms |
15352 KB |
91845 numbers |
| 27 |
Correct |
1291 ms |
15992 KB |
98296 numbers |
| 28 |
Correct |
1046 ms |
14584 KB |
85384 numbers |
| 29 |
Correct |
1031 ms |
14588 KB |
85317 numbers |
| 30 |
Correct |
1161 ms |
15996 KB |
98246 numbers |
| 31 |
Correct |
610 ms |
13304 KB |
50001 numbers |
