oj.uz

Submission #1044183

# Submission time Handle Problem Language Result Execution time Memory
1044183 2024-08-05T07:53:34 Z vjudge1 Svjetlost (COI18_svjetlost) C++17
40 / 100
 3000 ms 9936 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long double
#define point pair<int,int>
#define x first
#define y second
int const pi=3.141592653589793;
int const oe=180;

int angle(point p1,point p2){
    int deltaY = p2.y - p1.y;
    int deltaX = p2.x - p1.x;
    int dg = (atan2(deltaY, deltaX) * oe) / pi;
    if(dg<0)
        dg+=360;
    return dg;
}

bool check(int a1,int a2){
    if(a1<=180)
        return (a2<a1) || (a2>a1+oe);
    else
        return (a2>a1-oe && a2<a1);
}
int dist(point a,point b){
    return sqrt(((a.x-b.x)*(a.x-b.x))+((a.y-b.y)*(a.y-b.y)));
}

int solve(vector<point> pts){
    int n=pts.size();
    if(n==1)
        return 0;
    else if(n==2)
        return dist(pts[0],pts[1]);
    for (int i = 0; i < n; ++i){
        pts.push_back(pts[i]);
    }
    int len=dist(pts[0],pts[1])+dist(pts[1],pts[2]);
    int maxx=len;
    int p1=0,p2=2;
    int a=0,b=2;
    while(p1<n){
        int a1=angle(pts[p1],pts[p1+1]);
        int a2=angle(pts[p2+1],pts[p2]);
        // cout<<a1<<' '<<a2<<endl;
        if(p2+1<p1+n && a1!=a2 && check(a1,a2)){
            len+=dist(pts[p2],pts[p2+1]);
            p2+=1;
        }
        else{
            len-=dist(pts[p1],pts[p1+1]);
            p1+=1;
        }
        if(len>maxx){
            maxx=len;
            a=p1,b=p2;
        }
        // maxx=max(maxx,len);
    }
    // cout<<a<<' '<<b<<endl;
    return maxx;
}

signed main(){
    int n;
    cin>>n;
    vector<point> pts(n);
    for (int i = 0; i < n; ++i)
        cin>>pts[i].x>>pts[i].y;
    cout<<fixed;
    cout<<setprecision(10)<<solve(pts)<<endl;;
    int q;
    cin>>q;
    vector<bool> del(n,0);
    while(q--){
        int d;
        cin>>d;
        del[d-1]=1;
        vector<point> p;
        for (int i = 0; i < n; ++i)
            if(del[i]==0)
                p.push_back(pts[i]);
        cout<<solve(p)<<endl;
    }
    return 0;
}

Compilation message

svjetlost.cpp: In function 'long double solve(std::vector<std::pair<long double, long double> >)':
svjetlost.cpp:41:9: warning: variable 'a' set but not used [-Wunused-but-set-variable]
   41 |     int a=0,b=2;
      |         ^
svjetlost.cpp:41:13: warning: variable 'b' set but not used [-Wunused-but-set-variable]
   41 |     int a=0,b=2;
      |             ^

Subtask #1
12.0 / 12.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB 11 numbers
2 Correct 2 ms 348 KB 41 numbers
3 Correct 1 ms 348 KB 11 numbers
4 Correct 3 ms 348 KB 93 numbers
5 Correct 51 ms 632 KB 101 numbers
6 Correct 415 ms 716 KB 1201 numbers
7 Correct 610 ms 772 KB 1556 numbers
8 Correct 970 ms 880 KB 1996 numbers
9 Correct 863 ms 808 KB 1960 numbers
10 Correct 908 ms 840 KB 1991 numbers
11 Correct 976 ms 784 KB 1963 numbers

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB found '32934.3604541195', expected '32934.3604541195', error '0.0000000000'
2 Correct 2 ms 604 KB found '31571636.3365447670', expected '31571636.3365447633', error '0.0000000000'
3 Correct 12 ms 1520 KB found '31442617.6286691166', expected '31442617.6286691241', error '0.0000000000'
4 Correct 22 ms 2384 KB found '31424400.0534066260', expected '31424400.0534067489', error '0.0000000000'
5 Correct 90 ms 9936 KB found '3142086769.6889743805', expected '3142086769.6889681816', error '0.0000000000'
6 Correct 92 ms 8536 KB found '3142076120.8714599609', expected '3142076120.8714694977', error '0.0000000000'

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 892 ms 1008 KB 1001 numbers
2 Execution timed out 3058 ms 5108 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB 11 numbers
2 Correct 2 ms 348 KB 41 numbers
3 Correct 1 ms 348 KB 11 numbers
4 Correct 3 ms 348 KB 93 numbers
5 Correct 51 ms 632 KB 101 numbers
6 Correct 415 ms 716 KB 1201 numbers
7 Correct 610 ms 772 KB 1556 numbers
8 Correct 970 ms 880 KB 1996 numbers
9 Correct 863 ms 808 KB 1960 numbers
10 Correct 908 ms 840 KB 1991 numbers
11 Correct 976 ms 784 KB 1963 numbers
12 Correct 0 ms 348 KB found '32934.3604541195', expected '32934.3604541195', error '0.0000000000'
13 Correct 2 ms 604 KB found '31571636.3365447670', expected '31571636.3365447633', error '0.0000000000'
14 Correct 12 ms 1520 KB found '31442617.6286691166', expected '31442617.6286691241', error '0.0000000000'
15 Correct 22 ms 2384 KB found '31424400.0534066260', expected '31424400.0534067489', error '0.0000000000'
16 Correct 90 ms 9936 KB found '3142086769.6889743805', expected '3142086769.6889681816', error '0.0000000000'
17 Correct 92 ms 8536 KB found '3142076120.8714599609', expected '3142076120.8714694977', error '0.0000000000'
18 Correct 892 ms 1008 KB 1001 numbers
19 Execution timed out 3058 ms 5108 KB Time limit exceeded
20 Halted 0 ms 0 KB -