#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cassert>
#include <vector>
#include <cmath>
#include <set>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair <ll, ll> point;
#define X first
#define Y second
point operator- (point a, point b) {
return point(a.X - b.X, a.Y - b.Y);
}
ll operator* (point a, point b) {
return a.X * b.Y - a.Y * b.X;
}
bool intersect (point a, point b, point c, point d) {
point v = b - a, u = c - d;
if (u * v == 0)
return false;
if (0 < (u * v))
return (u * v) <= ((a - d) * v);
return (u * v) >= ((a - d) * v);
}
ld distance (point a, point b) {
return sqrt((a.X - b.X) * (a.X - b.X) + (a.Y - b.Y) * (a.Y - b.Y));
}
const ll N = 1e5 + 5, inf = 10000000LL * 10000000LL;
int n, q, K, K2, K3, fr, bc;
point p[N];
ld res[N << 2], l1, l2;
ld RES[N];
ld lazy[N << 2];
ld len[N << 2];
ld LEN[N];
set <int> live;
int dist (int a, int b) {
return a < b? b - a: n - a + b;
}
int nxt (int a) {
if (live.lower_bound(a + 1) != live.end())
return *live.lower_bound(a + 1);
return *live.begin();
}
int prv (int a) {
if (live.lower_bound(a) != live.begin())
return *(--live.lower_bound(a));
return *(--live.end());
}
ld getLen (int l, int r, int s = 0, int e = n, int id = 1) {
if (l <= s && e <= r)
return len[id];
if (r <= s || e <= l)
return 0;
int mid = e + s >> 1;
return getLen(l, r, s, mid, id << 1) + getLen(l, r, mid, e, id << 1 | 1);
}
void updLen (int tmp, ld val, int s = 0, int e = n, int id = 1) {
if (e - s == 1) {
len[id] = val;
return ;
}
int mid = e + s >> 1;
if (tmp < mid)
updLen(tmp, val, s, mid, id << 1);
else
updLen(tmp, val, mid, e, id << 1 | 1);
len[id] = len[id << 1] + len[id << 1 | 1];
}
ld calcLen (int l, int r) {
if (l <= r)
return getLen(l, r + 1);
return getLen(l, n) + getLen(0, r + 1);
}
int calc (int d) {
int cnt = 0;
int s = nxt(d), e = d;
while (nxt(s) != e) {
cnt++;
int mid = (s + dist(s, e) / 2) % n;
if (nxt(mid) == e)
mid = prv(nxt(mid));
else
mid = nxt(prv(mid));
if (intersect(p[d], p[nxt(d)], p[mid], p[nxt(mid)]))
s = mid;
else
e = mid;
}
assert(cnt <= 20);
return s;
}
int calcRev (int d) {
int s = d, e = prv(d);
while (nxt(s) != e) {
int mid = (s + dist(s, e) / 2) % n;
if (nxt(mid) == e)
mid = prv(nxt(mid));
else
mid = nxt(prv(mid));
if (intersect(p[mid], p[nxt(mid)], p[d], p[nxt(d)]))
e = mid;
else
s = mid;
}
return e;
}
void buildLen (int s = 0, int e = n, int id = 1) {
if (e - s == 1) {
LEN[s] = distance(p[s], p[nxt(s)]);
len[id] = LEN[s];
return ;
}
int mid = e + s >> 1;
buildLen(s, mid, id << 1);
buildLen(mid, e, id << 1 | 1);
len[id] = len[id << 1] + len[id << 1 | 1];
}
void buildResLst (int s = 0, int e = n, int id = 1) {
if (e - s == 1) {
res[id] = RES[s];
return ;
}
int mid = e + s >> 1;
buildResLst(s, mid, id << 1);
buildResLst(mid, e, id << 1 | 1);
res[id] = max(res[id << 1], res[id << 1 | 1]);
}
void preProcess() {
for (int i = 0; i < n; i++)
live.insert(i);
buildLen();
int r = 1;
ld sum = LEN[0];
for (int l = 0; l < n; l++) {
while (intersect(p[l], p[(l + 1) % n], p[r], p[(r + 1) % n])) {
sum += LEN[r];
r = (r + 1) % n;
}
RES[l] = sum;
sum -= LEN[l];
}
buildResLst();
}
void shift (int id) {
res[id << 1] += lazy[id];
lazy[id << 1] += lazy[id];
res[id << 1 | 1] += lazy[id];
lazy[id << 1 | 1] += lazy[id];
lazy[id] = 0;
}
void setRes (int tmp, ld val, int s = 0, int e = n, int id = 1) {
if (e - s == 1) {
res[id] = val;
return ;
}
if (lazy[id])
shift(id);
int mid = e + s >> 1;
if (tmp < mid)
setRes(tmp, val, s, mid, id << 1);
else
setRes(tmp, val, mid, e, id << 1 | 1);
res[id] = max(res[id << 1], res[id << 1 | 1]);
}
void updRes (int l, int r, ld val, int s = 0, int e = n, int id = 1) {
if (l <= s && e <= r) {
res[id] += val;
lazy[id] += val;
return ;
}
if (r <= s || e <= l)
return ;
if (lazy[id])
shift(id);
int mid = e + s >> 1;
updRes(l, r, val, s, mid, id << 1);
updRes(l, r, val, mid, e, id << 1 | 1);
res[id] = max(res[id << 1], res[id << 1 | 1]);
}
void calcRes (int l, int r, ld val) {
if (l <= r)
updRes(l, r + 1, val);
else {
updRes(l, n, val);
updRes(0, r + 1, val);
}
}
void delate (int id) {
K2 = calcRev(prv(id));
live.erase(id);
fr = nxt(id);
bc = prv(id);
K = calcRev(id);
K3 = calcRev(bc);
l1 = distance(p[bc], p[id]);
l2 = distance(p[bc], p[fr]);
updLen(id, 0);
updLen(bc, distance(p[bc], p[fr]));
setRes(id, -inf);
setRes(bc, calcLen(bc, calc(bc)));
if (K != bc)
calcRes(K, prv(bc), - l1 - distance(p[id], p[fr]) + l2);
if (K3 != K)
calcRes(K3, prv(K), - l1 + l2);
if (K2 != K3)
calcRes(K2, prv(K3), - l1);
}
int main() {
scanf("%d", &n);
for (int i = 0; i < n; i++)
scanf("%lld %lld", &p[i].X, &p[i].Y);
preProcess();
printf("%5LF\n", res[1]);
scanf("%d", &q);
while (q--) {
int id;
scanf("%d", &id);
id--;
delate(id);
printf("%5LF\n", res[1]);
}
return 0;
}
Compilation message
svjetlost.cpp: In function 'ld getLen(int, int, int, int, int)':
svjetlost.cpp:71:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = e + s >> 1;
~~^~~
svjetlost.cpp: In function 'void updLen(int, ld, int, int, int)':
svjetlost.cpp:80:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = e + s >> 1;
~~^~~
svjetlost.cpp: In function 'void buildLen(int, int, int)':
svjetlost.cpp:137:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = e + s >> 1;
~~^~~
svjetlost.cpp: In function 'void buildResLst(int, int, int)':
svjetlost.cpp:149:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = e + s >> 1;
~~^~~
svjetlost.cpp: In function 'void setRes(int, ld, int, int, int)':
svjetlost.cpp:192:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = e + s >> 1;
~~^~~
svjetlost.cpp: In function 'void updRes(int, int, ld, int, int, int)':
svjetlost.cpp:212:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = e + s >> 1;
~~^~~
svjetlost.cpp: In function 'int main()':
svjetlost.cpp:252:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
~~~~~^~~~~~~~~~
svjetlost.cpp:254:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld %lld", &p[i].X, &p[i].Y);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
svjetlost.cpp:258:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &q);
~~~~~^~~~~~~~~~
svjetlost.cpp:261:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &id);
~~~~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
11 numbers |
| 2 |
Correct |
5 ms |
384 KB |
41 numbers |
| 3 |
Correct |
5 ms |
384 KB |
11 numbers |
| 4 |
Correct |
6 ms |
384 KB |
93 numbers |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
11 numbers |
| 2 |
Correct |
5 ms |
384 KB |
41 numbers |
| 3 |
Correct |
5 ms |
384 KB |
11 numbers |
| 4 |
Correct |
6 ms |
384 KB |
93 numbers |
| 5 |
Correct |
8 ms |
512 KB |
101 numbers |
| 6 |
Correct |
35 ms |
640 KB |
1201 numbers |
| 7 |
Correct |
46 ms |
768 KB |
1556 numbers |
| 8 |
Correct |
59 ms |
768 KB |
1996 numbers |
| 9 |
Correct |
45 ms |
768 KB |
1960 numbers |
| 10 |
Correct |
47 ms |
768 KB |
1991 numbers |
| 11 |
Correct |
42 ms |
768 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 |
6 ms |
640 KB |
found '31571636.3365450017', expected '31571636.3365447633', error '0.0000000000' |
| 3 |
Correct |
13 ms |
2432 KB |
found '31442617.6286690012', expected '31442617.6286691241', error '0.0000000000' |
| 4 |
Correct |
20 ms |
4344 KB |
found '31424400.0534069985', expected '31424400.0534067489', error '0.0000000000' |
| 5 |
Correct |
77 ms |
16632 KB |
found '3142086769.6889739037', expected '3142086769.6889681816', error '0.0000000000' |
| 6 |
Correct |
77 ms |
16632 KB |
found '3142076120.8714599609', expected '3142076120.8714694977', error '0.0000000000' |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
36 ms |
1024 KB |
1001 numbers |
| 2 |
Correct |
576 ms |
6136 KB |
15001 numbers |
| 3 |
Correct |
1700 ms |
12024 KB |
44445 numbers |
| 4 |
Correct |
1405 ms |
20788 KB |
22223 numbers |
| 5 |
Execution timed out |
3083 ms |
22636 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
11 numbers |
| 2 |
Correct |
5 ms |
384 KB |
41 numbers |
| 3 |
Correct |
5 ms |
384 KB |
11 numbers |
| 4 |
Correct |
6 ms |
384 KB |
93 numbers |
| 5 |
Correct |
8 ms |
512 KB |
101 numbers |
| 6 |
Correct |
35 ms |
640 KB |
1201 numbers |
| 7 |
Correct |
46 ms |
768 KB |
1556 numbers |
| 8 |
Correct |
59 ms |
768 KB |
1996 numbers |
| 9 |
Correct |
45 ms |
768 KB |
1960 numbers |
| 10 |
Correct |
47 ms |
768 KB |
1991 numbers |
| 11 |
Correct |
42 ms |
768 KB |
1963 numbers |
| 12 |
Correct |
5 ms |
384 KB |
found '32934.3604540000', expected '32934.3604541195', error '0.0000000000' |
| 13 |
Correct |
6 ms |
640 KB |
found '31571636.3365450017', expected '31571636.3365447633', error '0.0000000000' |
| 14 |
Correct |
13 ms |
2432 KB |
found '31442617.6286690012', expected '31442617.6286691241', error '0.0000000000' |
| 15 |
Correct |
20 ms |
4344 KB |
found '31424400.0534069985', expected '31424400.0534067489', error '0.0000000000' |
| 16 |
Correct |
77 ms |
16632 KB |
found '3142086769.6889739037', expected '3142086769.6889681816', error '0.0000000000' |
| 17 |
Correct |
77 ms |
16632 KB |
found '3142076120.8714599609', expected '3142076120.8714694977', error '0.0000000000' |
| 18 |
Correct |
36 ms |
1024 KB |
1001 numbers |
| 19 |
Correct |
576 ms |
6136 KB |
15001 numbers |
| 20 |
Correct |
1700 ms |
12024 KB |
44445 numbers |
| 21 |
Correct |
1405 ms |
20788 KB |
22223 numbers |
| 22 |
Execution timed out |
3083 ms |
22636 KB |
Time limit exceeded |
