Submission #240822

#	Time	Username	Problem	Language	Result	Execution time	Memory
240822		VEGAnn	Svjetlost (COI18_svjetlost)	C++14	40 / 100	3081 ms	2340 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;

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;
//
//    cerr << a[0] << " " << a[1] << '\n';
//    cerr << b[0] << " " << b[1] << '\n';
//    cerr << c[0] << " " << c[1] << '\n';
//    cerr << d[0] << " " << d[1] << '\n';
//    cerr << '\n';

    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);
        }

        if (sum - E > ans)
            ans = sum;
    }

    cout << fixed << setprecision(10) << ans << '\n';
}

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];

    ans();

    int qq; cin >> qq;

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

        ans();
    }

    return 0;
}

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