#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;
}
};
tournament T;
tournament1 T1;
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));
}
bool cmp(pair < int, int > a, pair < int, int > b){
return atan2(a.second, a.first)<atan2(b.second, b.first);
}
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]));
}
}
// sort(vektor, vektor+n, cmp);
/* for(int i=0; i<n; i++){
cout << vektor[i].first << " " << vektor[i].second << '\n';
cout << atan2(vektor[i].second, vektor[i].first) << '\n';
}*/
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;
if(ccw({0, 0}, vektor[a], vektor[(x+1)%n])==0){
x=(x+1)%n;
}
x=(x+1)%n;
// 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=(binary(lij[a])+lij[a])%n;
if(ccw({0, 0}, vektor[lij[a]], vektor[(x+1)%n])==0){
x=(x+1)%n;
}
x=(x+1)%n;
// cout << lij[a] << " " << x << endl;
// 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};
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=(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[(x+1)%n])==0){
x=(x+1)%n;
}
x=(x+1)%n;
/* 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 |
1 ms |
512 KB |
11 numbers |
| 2 |
Incorrect |
1 ms |
512 KB |
38th numbers differ - expected: '38191.7444325295', found: '39498.9584580000', error = '0.0342276595' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
512 KB |
11 numbers |
| 2 |
Incorrect |
1 ms |
512 KB |
38th numbers differ - expected: '38191.7444325295', found: '39498.9584580000', error = '0.0342276595' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
512 KB |
found '32934.3604540000', expected '32934.3604541195', error '0.0000000000' |
| 2 |
Correct |
2 ms |
640 KB |
found '31571636.3365450017', expected '31571636.3365447633', error '0.0000000000' |
| 3 |
Correct |
7 ms |
1536 KB |
found '31442617.6286690012', expected '31442617.6286691241', error '0.0000000000' |
| 4 |
Correct |
16 ms |
2428 KB |
found '31424400.0534069985', expected '31424400.0534067489', error '0.0000000000' |
| 5 |
Correct |
52 ms |
8312 KB |
found '3142086769.6889629364', expected '3142086769.6889681816', error '0.0000000000' |
| 6 |
Correct |
53 ms |
8312 KB |
found '3142076120.8714442253', expected '3142076120.8714694977', error '0.0000000000' |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
768 KB |
573rd numbers differ - expected: '1043227215.3493254185', found: '1046037162.4037640095', error = '0.0026935139' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
512 KB |
11 numbers |
| 2 |
Incorrect |
1 ms |
512 KB |
38th numbers differ - expected: '38191.7444325295', found: '39498.9584580000', error = '0.0342276595' |
| 3 |
Halted |
0 ms |
0 KB |
- |
