#include <bits/stdc++.h>
using namespace std;
#define FOR(i, j, k) for(int i=(j); i<=(k); i++)
#define FFOR(i, j, k) for(int i=(j); i<(k); i++)
#define DFOR(i, j, k) for(int i=(j); i>=(k); i--)
#define bug(x) cerr<<#x<<" = "<<(x)<<'\n'
#define pb push_back
#define mp make_pair
#define bit(s, i) (((s)>>(i))&1LL)
#define mask(i) ((1LL<<(i)))
#define builtin_popcount __builtin_popcountll
#define __builtin_popcount __builtin_popcountll
using ll=long long; using ld=long double;
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count()); const ld pi=acos(0)*2;
template <typename T> inline void read(T &x){char c; bool nega=0; while((!isdigit(c=getchar()))&&(c!='-')); if(c=='-'){nega=1; c=getchar();} x=c-48; while(isdigit(c=getchar())) x=x*10+c-48; if(nega) x=-x;}
template <typename T> inline void writep(T x){if(x>9) writep(x/10); putchar(x%10+48);}
template <typename T> inline void write(T x){if(x<0){ putchar('-'); x=-x;} writep(x);}
template <typename T> inline void writeln(T x){write(x); putchar('\n');}
template <typename CT, typename T> inline void reset_container(CT &c, int sz, T v){c.resize(sz); for(auto &x: c) x=v;}
#define taskname "Svjetlost"
int n;
ld shifted3=((ld)(rng()%10000));
ld shifted2=((ld)(rng()%10000));
ld shifted=((ld)(rng()%100000))/100000;
class point{
public:
ld x, y;
void input(){
read(x);
read(y);
///(x+yi)*(cos(theta)+sin(theta)i);
///x=xcos-ysin
///y=xsin+ycos
x+=shifted2;
y+=shifted3;
ld nx=x*cos(shifted)-y*sin(shifted);
ld ny=x*sin(shifted)+y*cos(shifted);
x=nx;
y=ny;
// cerr<<x<<' '<<y<<'\n';
}
} p[100001];
class node{
public:
using pointer=node*;
int id;
pointer next, prev;
};
node nd[100001];
int k[100001];
ld r=1e10;
class line{
public:
ld a, b, c;
line(point A, point B){
a=A.y-B.y;
b=B.x-A.x;
c=-(A.x*a+A.y*b);
}
ld when_y_0(){
return -c/a;
}
ld when_x_0(){
return -c/b;
}
};
vector <pair <int, pair<int, int>>> queries;
vector <ld> v;
class segment_tree{
public:
using pointer=segment_tree*;
ld l, r;
ld value;
ld lazy;
pointer left, right;
segment_tree(int idl, int idr){
l=v[idl];
r=v[idr];
int idm=(idl+idr)/2;
value=lazy=0;
if(idl!=idr){
left=new segment_tree(idl, idm);
right=new segment_tree(idm+1, idr);
}
else left=right=nullptr;
}
void down(){
left->value+=lazy;
right->value+=lazy;
left->lazy+=lazy;
right->lazy+=lazy;
lazy=0;
}
void update(ld u, ld v, ld x){
if(l>v||r<u) return;
else if(u<=l&&v>=r){
value+=x;
lazy+=x;
}
else{
down();
left->update(u, v, x);
right->update(u, v, x);
value=max(left->value, right->value);
}
}
};
segment_tree::pointer tree;
pair <ld, ld> get_cut(point A, point B){
line L(A, B);
ld y0=L.when_x_0();
ld x0=L.when_y_0();
ld h=abs(x0)*abs(y0)/(sqrt(x0*x0+y0*y0));
ld theta=acosl(h/r);
ld alpha;
if(x0>0){
if(y0>0){
alpha=acos(h/x0);
}
else{
alpha=pi*2-acos(h/x0);
}
}
else{
if(y0>0){
alpha=pi-acos(h/-x0);
}
else{
alpha=pi+acos(h/-x0);
}
}
///alpha+=theta
ld f=alpha-theta;
if(f<0) f+=pi*2;
ld s=alpha+theta;
if(s>pi*2) s-=pi*2;
if(A.x*B.y-B.x*A.y<0) swap(f, s);
return mp(f, s);
}
void fake(int a, int b){
auto P=get_cut(p[a], p[b]);
v.pb(P.first);
v.pb(P.second);
}
void update_range(ld u, ld v, ld w){
if(u>v){
tree->update(u, pi*2, w);
tree->update(0, v, w);
}
else{
tree->update(u, v, w);
}
}
void update(int a, int b, int w){
auto P=get_cut(p[a], p[b]);
// cerr<<a<<' '<<b<<'\n';
// cerr<<P.first<<' '<<P.second<<'\n';
update_range(P.first, P.second, sqrt((p[a].x-p[b].x)*(p[a].x-p[b].x)+(p[a].y-p[b].y)*(p[a].y-p[b].y))*w);
}
int main(){
#ifdef Aria
if(fopen(taskname".in", "r"))
freopen(taskname".in", "r", stdin);
#endif // Aria
read(n);
FOR(i, 1, n) p[i].input();
int q;
read(q);
FOR(i, 1, n){
nd[i].id=i;
nd[i].next=&nd[i%n+1];
nd[i%n+1].prev=&nd[i];
}
FOR(i, 1, q){
int k;
read(k);
int a=nd[k].prev->id;
int b=nd[k].next->id;
nd[k].prev->next=nd[k].next;
nd[k].next->prev=nd[k].prev;
queries.pb(mp(k, mp(a, b)));
}
v.pb(0);
v.pb(pi*2);
FOR(i, 1, n) fake(i, i%n+1);
for(auto q: queries){
fake(q.second.first, q.first);
fake(q.first, q.second.second);
fake(q.second.first, q.second.second);
}
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
tree=new segment_tree(0, v.size()-1);
FOR(i, 1, n) update(i, i%n+1, 1);
cout<<setprecision(6)<<fixed<<tree->value<<'\n';
for(auto q: queries){
update(q.second.first, q.first, -1);
update(q.first, q.second.second, -1);
update(q.second.first, q.second.second, 1);
cout<<setprecision(6)<<fixed<<tree->value<<'\n';
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
11 numbers |
| 2 |
Correct |
2 ms |
376 KB |
41 numbers |
| 3 |
Correct |
2 ms |
376 KB |
11 numbers |
| 4 |
Correct |
3 ms |
368 KB |
93 numbers |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
11 numbers |
| 2 |
Correct |
2 ms |
376 KB |
41 numbers |
| 3 |
Correct |
2 ms |
376 KB |
11 numbers |
| 4 |
Correct |
3 ms |
368 KB |
93 numbers |
| 5 |
Correct |
5 ms |
888 KB |
101 numbers |
| 6 |
Correct |
14 ms |
1652 KB |
1201 numbers |
| 7 |
Incorrect |
19 ms |
1912 KB |
1st numbers differ - expected: '3158689889.6960182190', found: '2958274904.5891652107', error = '0.0634487690' |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
376 KB |
found '32934.3604540000', expected '32934.3604541195', error '0.0000000000' |
| 2 |
Incorrect |
7 ms |
1016 KB |
1st numbers differ - expected: '31571636.3365447633', found: '31560685.6790690012', error = '0.0003468511' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
2036 KB |
1st numbers differ - expected: '1042655967.3918291330', found: '1027855890.4960839748', error = '0.0141945928' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
11 numbers |
| 2 |
Correct |
2 ms |
376 KB |
41 numbers |
| 3 |
Correct |
2 ms |
376 KB |
11 numbers |
| 4 |
Correct |
3 ms |
368 KB |
93 numbers |
| 5 |
Correct |
5 ms |
888 KB |
101 numbers |
| 6 |
Correct |
14 ms |
1652 KB |
1201 numbers |
| 7 |
Incorrect |
19 ms |
1912 KB |
1st numbers differ - expected: '3158689889.6960182190', found: '2958274904.5891652107', error = '0.0634487690' |
| 8 |
Halted |
0 ms |
0 KB |
- |
