Submission #240840

#	Time	Username	Problem	Language	Result	Execution time	Memory
240840		VEGAnn	Svjetlost (COI18_svjetlost)	C++14	14 / 100	38 ms	7928 KiB

Main

#include <bits/stdc++.h>
#define PB push_back
#define all(x) x.begin(),x.end()
#define sz(x) ((int)x.size())
#define i2 array<int,2>
#define l2 array<ll,2>
using namespace std;
typedef long double ld;
typedef long long ll;
const int N = 100100;
const ld E = 1e-9;
vector<i2> pts;
bool mrk[N];
int x[N], y[N], n, nt[N], pr[N];
ld st[4 * N], psh[4 * N], cans[N];

ld sqr(ld x){ return x * x;}

ld dist(i2 a, i2 b){
    return sqrt(sqr(a[0] - b[0]) + sqr(a[1] - b[1]));
}

int next(int i) { return (i + 1) % sz(pts); }

ll area(i2 a, i2 b, i2 c){
    return (ll)(a[0] - b[0]) * (a[1] - c[1]) - (ll)(a[1] - b[1]) * (a[0] - c[0]);
}

bool ok(i2 a, i2 b, i2 c, i2 d){
    i2 cand = d;

    cand[0] += -c[0] + b[0];
    cand[1] += -c[1] + b[1];

    return area(a, b, cand) > 0;
}

void ans(){
    pts.clear();

    for (int i = 0; i < n; i++)
        if (!mrk[i])
            pts.PB({x[i], y[i]});

    ld ans = 0, sum = dist(pts[0], pts[1]);

    for (int i = 0, j = 1; i < sz(pts); i++){
        if (i > 0)
            sum -= dist(pts[i], pts[i - 1]);

        while (ok(pts[i], pts[next(i)], pts[j], pts[next(j)])) {
            sum += dist(pts[j], pts[next(j)]);
            j = next(j);
        }

        cans[i] = sum;
    }
}

void build(int v, int l, int r){
    if (l == r){
        st[v] = cans[l];

        return;
    }

    int md = (l + r) >> 1;

    build(v + v, l, md);
    build(v + v + 1, md + 1, r);

    st[v] = max(st[v + v], st[v + v + 1]);
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

#ifdef _LOCAL
    freopen("in.txt","r",stdin);
#endif // _LOCAL

    cin >> n;

    for (int i = 0; i < n; i++) {
        cin >> x[i] >> y[i];
        nt[i] = (i + 1) % n;
        pr[i] = (i - 1 + n) % n;
    }

    ans();

    build(1, 0, n - 1);

    cout << fixed << setprecision(10) << st[1];

//    int qq; cin >> qq;
//
//    for (; qq; qq--){
//        int x; cin >> x; x--;
//        mrk[x] = 1;
//
//        ans();
//    }

    return 0;
}

Compilation message (stderr)

svjetlost.cpp: In function 'void ans()':
svjetlost.cpp:45:8: warning: unused variable 'ans' [-Wunused-variable]
     ld ans = 0, sum = dist(pts[0], pts[1]);
        ^~~

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