Submission #127367

#	Time	Username	Problem	Language	Result	Execution time	Memory
127367		JohnTitor	Svjetlost (COI18_svjetlost)	C++11	100 / 100	1511 ms	95036 KiB

Main

#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=1e20;
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);
    ios_base::sync_with_stdio(false);
    cout.tie(NULL);
    cout<<setprecision(16)<<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(16)<<tree->value<<'\n';
    }
}

• Subtask 1: 12 / 12
• Subtask 2: 14 / 14
• Subtask 3: 14 / 14
• Subtask 4: 29 / 29
• Subtask 5: 31 / 31