Submission #1358964

#TimeUsernameProblemLanguageResultExecution timeMemory
1358964gkos5678Svjetlost (COI18_svjetlost)C++20
0 / 100
0 ms0 KiB
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define ff first
#define ss second

typedef long long ll;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;

const int maxn = 1e5 + 7;

ll n, q, x[maxn], y[maxn], k[maxn];
double ps[maxn];
bool in[maxn];
vpll p;

ll ccw(pll a, pll b, pll c){
    return a.ff * (b.ss - c.ss) + b.ff * (c.ss - a.ss) + c.ff * (a.ss - b.ss);
}

double rijesi(){
    int m = p.size() - 1;
    for (int i = 1; i <= m; i++){
        ll sms = pow(p[i].ff - p[i % m + 1].ff, 2) + pow(p[i % m + 1].ss - p[i].ss, 2);
        ps[i] = ps[i - 1] + sqrt(sms);
    }
    double ans = 0;
    for (int i = 1; i <= m; i++){
        int l = i + 1, r = i + m - 1;
        while(l < r){
            int mi = (l + r + 1) / 2;
            if (mi > m)
                mi -= m;
            pll p1 = p[mi], p2 = p[mi % m + 1];
            pll p3 = {p1.ff + p[i].ff - p[i % m + 1].ff, p1.ss + p[i].ss - p[i % m + 1].ss};
            if (mi < l) mi += m;
            if (ccw(p1, p2, p3) > 0)
                l = mi;
            else
                r = mi - 1;
        }
        if (l > m) l -= m;
        double tr = ps[l] - ps[i - 1];
        if (tr < 0) tr += ps[m];
        ans = max(ans, tr);
    }
    return ans;
}

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

    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> x[i] >> y[i];
    cin >> q;
    for (int i = 1; i <= q; i++)
        cin >> k[i];

    for (int i = 1; i <= n; i++)
        in[i] = 1;
    for (int i = 1; i <= q + 1; i++){
        p.clear();
        p.pb({0, 0});
        for (int j = 1; j <= n; j++)
            if (in[j]) p.pb({x[j], y[j]});
        cout << fixed << setprecision(9) << rijesi() << "\n";
        in[k[i]] = 0;
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...