#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
#include<iomanip>
using namespace std;
using pii = pair<int, int>;
using ll = long long;
using ld = long double;
#define forn(i, n) for(int i=0; i<(int)n; ++i)
#define PB push_back
#define F first
#define S second
struct node{
int vind, eind;
node *pr, *nxt;
node(int VI=0, int EI=0, node* PR=NULL, node* NX=NULL) : vind(VI), eind(EI), pr(PR), nxt(NX) {}
};
bool up(pii p){
return p.S>0 || (p.S==0 && p.F>0);
}
bool covers(pii p, pii q){
return ((ll)p.F)*q.S > ((ll)p.S)*q.F;
}
const int MAXN=100010;
int n, he, u, q, assi[2*MAXN], fin[2*MAXN];
pii pt[MAXN];
node* pol = new node;
node* ver[MAXN];
vector<int> del;
pii edge[2*MAXN];
pair<pii, int> lis[2*MAXN];
ld tr[4*MAXN], lazy[2*MAXN];
bool modif[MAXN];
void apply(int p, ld value){
if(p<u) lazy[p]+=value, modif[p]=true;
tr[p]+=value;
}
void push(int p){
for(int s=he; s>0; --s){
int i=p>>s;
if(modif[i]){
apply(i<<1, lazy[i]);
apply(i<<1|1, lazy[i]);
lazy[i]=0, modif[i]=false;
}
}
}
void build(int p){
for(; p>1; p>>=1) tr[p>>1] = max(tr[p], tr[p^1]) + lazy[p>>1];
}
void inc(int l, int r, ld value){
l+=u, r+=u;
int l0=l, r0=r;
for(; l<r; l>>=1, r>>=1){
if(l&1) apply(l++, value);
if(r&1) apply(--r, value);
}
build(l0);
build(r0-1);
}
void circ_inc(int l, int r, ld value){
if(l<r) inc(l, r, value);
else inc(l, u, value), inc(0, r, value);
}
ld query(int l, int r){
l+=u, r+=u;
push(l);
push(r-1);
ld ret=0;
for(; l<r; l>>=1, r>>=1){
if(l&1) ret=max(tr[l++], ret);
if(r&1) ret=max(tr[--r], ret);
}
return ret;
}
ld len(pii p){
return sqrtl(((ll)p.F)*p.F + ((ll)p.S)*p.S);
}
int main(){
scanf("%d", &n);
forn(i, n) scanf("%d %d", &pt[i].F, &pt[i].S);
node* cur=pol;
forn(i, n-1){
cur->nxt = new node(i+1, i+1, cur);
cur=cur->nxt;
}
cur->nxt=pol;
pol->pr=cur;
node* tmp=pol;
while(true){
ver[tmp->vind]=tmp;
tmp=tmp->nxt;
if(tmp==pol) break;
}
forn(i, n) edge[i]={pt[(i+1)%n].F - pt[i].F, pt[(i+1)%n].S - pt[i].S};
scanf("%d", &q);
int ecn=n;
forn(i, q){
int v; scanf("%d", &v); --v;
node *pr = ver[v]->pr, *nxt = ver[v]->nxt;
del.PB(pr->eind), del.PB(ver[v]->eind);
pii src = pt[pr->vind], dst = pt[nxt->vind];
edge[ecn] = make_pair(dst.F - src.F, dst.S - src.S);
pr->nxt=nxt, nxt->pr=pr;
pr->eind=ecn++;
}
forn(i, n+q) lis[i]={edge[i], i};
sort(lis, lis+n+q, [](pair<pii, int> a, pair<pii, int> b){
return up(a.F)==up(b.F)? ((ll)a.F.S)*b.F.F < ((ll)a.F.F)*b.F.S : up(a.F)>up(b.F);
});
u = n+q;
he = 8*sizeof(int) - __builtin_clz(u);
forn(i, u) assi[lis[i].S]=i;
int cuur=1;
forn(i, u){
while(covers(lis[i].F, lis[cuur].F)) cuur=(cuur+1)%u;
fin[i]=cuur;
}
cout << setprecision(9) << fixed;
forn(i, n) circ_inc(assi[i], fin[assi[i]], len(edge[i]));
cout << query(0, n) << "\n";
forn(i, q){
int i1=del[i<<1], i2=del[i<<1|1];
circ_inc(assi[i1], fin[assi[i1]], -len(edge[i1]));
circ_inc(assi[i2], fin[assi[i2]], -len(edge[i2]));
circ_inc(assi[n+i], fin[assi[n+i]], len(edge[n+i]));
cout << query(0, n) << "\n";
}
}
Compilation message
svjetlost.cpp: In function 'int main()':
svjetlost.cpp:94:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
94 | scanf("%d", &n);
| ~~~~~^~~~~~~~~~
svjetlost.cpp:95:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
95 | forn(i, n) scanf("%d %d", &pt[i].F, &pt[i].S);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
svjetlost.cpp:111:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
111 | scanf("%d", &q);
| ~~~~~^~~~~~~~~~
svjetlost.cpp:114:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
114 | int v; scanf("%d", &v); --v;
| ~~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
11 numbers |
| 2 |
Incorrect |
1 ms |
324 KB |
12th numbers differ - expected: '34973.6998323271', found: '34372.4877116250', error = '0.0171904066' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
11 numbers |
| 2 |
Incorrect |
1 ms |
324 KB |
12th numbers differ - expected: '34973.6998323271', found: '34372.4877116250', error = '0.0171904066' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
found '32934.3604541190', expected '32934.3604541195', error '0.0000000000' |
| 2 |
Correct |
2 ms |
488 KB |
found '31571636.3365447670', expected '31571636.3365447633', error '0.0000000000' |
| 3 |
Correct |
9 ms |
1876 KB |
found '31442617.6286691166', expected '31442617.6286691241', error '0.0000000000' |
| 4 |
Correct |
18 ms |
3284 KB |
found '31424400.0534066260', expected '31424400.0534067489', error '0.0000000000' |
| 5 |
Correct |
77 ms |
12584 KB |
found '3142086769.6889743805', expected '3142086769.6889681816', error '0.0000000000' |
| 6 |
Correct |
72 ms |
12604 KB |
found '3142076120.8714599609', expected '3142076120.8714694977', error '0.0000000000' |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
720 KB |
68th numbers differ - expected: '1042871452.8534376621', found: '1042655967.3918284178', error = '0.0002066271' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
11 numbers |
| 2 |
Incorrect |
1 ms |
324 KB |
12th numbers differ - expected: '34973.6998323271', found: '34372.4877116250', error = '0.0171904066' |
| 3 |
Halted |
0 ms |
0 KB |
- |
