oj.uz

Submission #240840

# Submission time Handle Problem Language Result Execution time Memory
240840 2020-06-21T09:49:43 Z VEGAnn Svjetlost (COI18_svjetlost) C++14
14 / 100
 38 ms 7928 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, 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

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 384 KB Unexpected end of file - double expected
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 384 KB Unexpected end of file - double expected
2 Halted 0 ms 0 KB -

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 512 KB found '31571636.3365447670', expected '31571636.3365447633', error '0.0000000000'
3 Correct 8 ms 1536 KB found '31442617.6286691166', expected '31442617.6286691241', error '0.0000000000'
4 Correct 12 ms 2304 KB found '31424400.0534066260', expected '31424400.0534067489', error '0.0000000000'
5 Correct 37 ms 7928 KB found '3142086769.6889743805', expected '3142086769.6889681816', error '0.0000000000'
6 Correct 38 ms 7920 KB found '3142076120.8714599609', expected '3142076120.8714694977', error '0.0000000000'

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 640 KB Unexpected end of file - double expected
2 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 384 KB Unexpected end of file - double expected
2 Halted 0 ms 0 KB -