#include <bits/stdc++.h>
#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " : " << x << '\n'
using namespace std;
typedef long long ll;
typedef double ld;
typedef string str;
typedef pair<ll, ll> pll;
const ll Mod = 1000000007LL;
const int N = 1e5 + 10;
const ll Inf = 2242545357980376863LL;
const ll Log = 30;
ld seg[N << 2];
ld lz[N << 2];
void Add(int id, int l, int r, ld x, int L, int R){
if((r <= L) || (R <= l)) return ;
if((l <= L) && (R <= r)){
lz[id] += x;
seg[id] += x;
return ;
}
int mid = (L + R) >> 1;
Add(id << 1, l, r, x, L, mid);
Add(id << 1 | 1, l, r, x, mid, R);
seg[id] = max(seg[id << 1], seg[id << 1 | 1]) + lz[id];
}
pll operator - (pll a, pll b){
return {a.F - b.F, a.S - b.S};
}
pll operator + (pll a, pll b){
return {a.F - b.F, a.S - b.S};
}
ll operator * (pll a, pll b){
return a.F * b.S - a.S * b.F;
}
typedef pair<pll, ll> nd;
struct CMP {
bool operator() (nd A, nd B) const {
pll a = A.F, b = B.F;
if(a == b) return A.S < B.S;
int fa = a < pll(0, 0);
int fb = b < pll(0, 0);
if(fa != fb) return fa > fb;
return a*b > 0;
}
};
multiset<nd, CMP> ms;
ll n;
ll nx[N], bf[N];
pll p[N];
int Match(int x){
pll e = p[x] - p[nx[x]];
auto it = ms.lower_bound({e, -1});
if(it == ms.begin()) it = --ms.end();
else it --;
return it -> S;
}
int RevMatch(int x){
int res = bf[bf[x]];
while((p[bf[x]] - p[x]) * (p[res] - p[nx[res]]) < 0) res = bf[res];
return nx[res];
}
ld Len(pll x){ return sqrt(x.F*x.F + x.S*x.S); }
void Add(int l, int r, ld ln){
if(l <= r){
Add(1, l, r + 1, ln, 0, n);
} else {
Add(1, l, n, ln, 0, n);
Add(1, 0, r + 1, ln, 0, n);
}
}
void Apply(int x, ld z){
Add(nx[x], Match(x), z*Len(p[nx[x]] - p[x]));
}
void Rem(int x){
int L, R;
Apply(bf[x], -1);
Apply(x, -1);
L = RevMatch(x);
R = RevMatch(nx[x]);
ms.erase(ms.find({p[nx[x]] - p[x], nx[x]}));
ms.erase(ms.find({p[x] - p[bf[x]], x}));
bf[nx[x]] = bf[x];
nx[bf[x]] = nx[x];
ms.insert({p[nx[x]] - p[bf[x]], nx[x]});
Apply(bf[x], 1);
Add(1, x, x + 1, -1e15, 0, n);
ld sm = 0;
//assert(L == R);
//cerr << L << ' ' << R << '\n';
while(L != R){
/*debug(L);
debug(((p[nx[L]] - p[L]) * (p[nx[x]] - p[bf[x]])));
debug((p[nx[L]] - p[L]).F);
debug((p[nx[L]] - p[L]).S);
debug((p[nx[x]] - p[bf[x]]).F);
debug((p[nx[x]] - p[bf[x]]).S);
*/
if( ((p[nx[L]] - p[L]) * (p[nx[x]] - p[bf[x]])) > 0) sm += Len(p[L] - p[nx[L]]);
L = nx[L];
}
//assert(sm == 0);
//assert(sm < 1);
//cerr << sm << '\n';
Add(1, nx[x], nx[x] + 1, sm, 0, n);
}
int main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n;
assert(n <= 2000);
for(int i = 0; i < n; i++)
cin >> p[i]. F >> p[i].S;
for(int i = 0; i < n; i++) nx[i] = (i + 1) % n;
for(int i = 0; i < n; i++) bf[nx[i]] = i;
for(int i = 0; i < n; i++)
ms.insert({ p[i] - p[bf[i]], i });
for(int i = 0; i < n; i++) Apply(i, 1);
cout << fixed << setprecision(6) << seg[1] << '\n';
//for(int i = 0; i < n; i++) cerr << i << ' ' << RevMatch(i) << ' ' << Match(i) << '\n';
ll Q;
cin >> Q;
int rm;
for(int i = 0; i < Q; i++){
cin >> rm;
rm --;
Rem(rm);
cout << fixed << setprecision(6) << seg[1] << '\n';
}
return 0;
}
/*
3
0 0
1 0
0 1
0
4
0 0
2 0
2 2
0 2
1
1
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
384 KB |
11 numbers |
2 |
Correct |
4 ms |
384 KB |
41 numbers |
3 |
Correct |
5 ms |
384 KB |
11 numbers |
4 |
Correct |
5 ms |
384 KB |
93 numbers |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
384 KB |
11 numbers |
2 |
Correct |
4 ms |
384 KB |
41 numbers |
3 |
Correct |
5 ms |
384 KB |
11 numbers |
4 |
Correct |
5 ms |
384 KB |
93 numbers |
5 |
Correct |
6 ms |
512 KB |
101 numbers |
6 |
Correct |
11 ms |
640 KB |
1201 numbers |
7 |
Correct |
14 ms |
640 KB |
1556 numbers |
8 |
Correct |
18 ms |
640 KB |
1996 numbers |
9 |
Correct |
17 ms |
640 KB |
1960 numbers |
10 |
Correct |
17 ms |
640 KB |
1991 numbers |
11 |
Correct |
17 ms |
640 KB |
1963 numbers |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
384 KB |
found '32934.3604540000', expected '32934.3604541195', error '0.0000000000' |
2 |
Correct |
5 ms |
512 KB |
found '31571636.3365450017', expected '31571636.3365447633', error '0.0000000000' |
3 |
Runtime error |
5 ms |
512 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
5 ms |
512 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
384 KB |
11 numbers |
2 |
Correct |
4 ms |
384 KB |
41 numbers |
3 |
Correct |
5 ms |
384 KB |
11 numbers |
4 |
Correct |
5 ms |
384 KB |
93 numbers |
5 |
Correct |
6 ms |
512 KB |
101 numbers |
6 |
Correct |
11 ms |
640 KB |
1201 numbers |
7 |
Correct |
14 ms |
640 KB |
1556 numbers |
8 |
Correct |
18 ms |
640 KB |
1996 numbers |
9 |
Correct |
17 ms |
640 KB |
1960 numbers |
10 |
Correct |
17 ms |
640 KB |
1991 numbers |
11 |
Correct |
17 ms |
640 KB |
1963 numbers |
12 |
Correct |
5 ms |
384 KB |
found '32934.3604540000', expected '32934.3604541195', error '0.0000000000' |
13 |
Correct |
5 ms |
512 KB |
found '31571636.3365450017', expected '31571636.3365447633', error '0.0000000000' |
14 |
Runtime error |
5 ms |
512 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
15 |
Halted |
0 ms |
0 KB |
- |