oj.uz

Submission #240822

# Submission time Handle Problem Language Result Execution time Memory
240822 2020-06-21T08:52:40 Z VEGAnn Svjetlost (COI18_svjetlost) C++14
40 / 100
 3000 ms 2340 KB 
#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.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB 11 numbers
2 Correct 5 ms 384 KB 41 numbers
3 Correct 5 ms 384 KB 11 numbers
4 Correct 5 ms 384 KB 93 numbers

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB 11 numbers
2 Correct 5 ms 384 KB 41 numbers
3 Correct 5 ms 384 KB 11 numbers
4 Correct 5 ms 384 KB 93 numbers
5 Correct 11 ms 384 KB 101 numbers
6 Correct 47 ms 504 KB 1201 numbers
7 Correct 65 ms 384 KB 1556 numbers
8 Correct 106 ms 384 KB 1996 numbers
9 Correct 88 ms 492 KB 1960 numbers
10 Correct 94 ms 636 KB 1991 numbers
11 Correct 97 ms 504 KB 1963 numbers

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB found '32934.3604541195', expected '32934.3604541195', error '0.0000000000'
2 Correct 5 ms 384 KB found '31571636.3365447670', expected '31571636.3365447633', error '0.0000000000'
3 Correct 8 ms 640 KB found '31442617.6286691166', expected '31442617.6286691241', error '0.0000000000'
4 Correct 11 ms 896 KB found '31424400.0534066260', expected '31424400.0534067489', error '0.0000000000'
5 Correct 36 ms 2340 KB found '3142086769.6889743805', expected '3142086769.6889681816', error '0.0000000000'
6 Correct 33 ms 2164 KB found '3142076120.8714599609', expected '3142076120.8714694977', error '0.0000000000'

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 512 KB 1001 numbers
2 Execution timed out 3081 ms 1308 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB 11 numbers
2 Correct 5 ms 384 KB 41 numbers
3 Correct 5 ms 384 KB 11 numbers
4 Correct 5 ms 384 KB 93 numbers
5 Correct 11 ms 384 KB 101 numbers
6 Correct 47 ms 504 KB 1201 numbers
7 Correct 65 ms 384 KB 1556 numbers
8 Correct 106 ms 384 KB 1996 numbers
9 Correct 88 ms 492 KB 1960 numbers
10 Correct 94 ms 636 KB 1991 numbers
11 Correct 97 ms 504 KB 1963 numbers
12 Correct 5 ms 384 KB found '32934.3604541195', expected '32934.3604541195', error '0.0000000000'
13 Correct 5 ms 384 KB found '31571636.3365447670', expected '31571636.3365447633', error '0.0000000000'
14 Correct 8 ms 640 KB found '31442617.6286691166', expected '31442617.6286691241', error '0.0000000000'
15 Correct 11 ms 896 KB found '31424400.0534066260', expected '31424400.0534067489', error '0.0000000000'
16 Correct 36 ms 2340 KB found '3142086769.6889743805', expected '3142086769.6889681816', error '0.0000000000'
17 Correct 33 ms 2164 KB found '3142076120.8714599609', expected '3142076120.8714694977', error '0.0000000000'
18 Correct 96 ms 512 KB 1001 numbers
19 Execution timed out 3081 ms 1308 KB Time limit exceeded
20 Halted 0 ms 0 KB -