oj.uz

Submission #13757

# Submission time Handle Problem Language Result Execution time Memory
13757 2015-04-01T06:52:27 Z baneling100 Wall construction (kriii2_WA) C++
4 / 4
 0 ms 1128 KB 
#include <stdio.h>
#include <algorithm>
#include <math.h>
#define N_MAX 1000
#define Pi 3.1415926535897932384626433832795

using namespace std;

struct column {
    int x;
    int y;
    bool operator < (column K) const {return x<K.x || (x==K.x && y<K.y);}
} A[N_MAX+1];
int N, R, Up[N_MAX+1], Usize, Down[N_MAX+1], Dsize;
double Res;

int turn(int a, int b, int c) {return (A[a].x*A[b].y+A[b].x*A[c].y+A[c].x*A[a].y)-(A[b].x*A[a].y+A[c].x*A[b].y+A[a].x*A[c].y);}

int main(void) {

    int i;

    scanf("%d %d",&N,&R);
    for(i=1 ; i<=N ; i++) scanf("%d %d",&A[i].x,&A[i].y);
    sort(A+1,A+N+1);
    Up[++Usize]=1;
    Up[++Usize]=2;
    Down[++Dsize]=1;
    Down[++Dsize]=2;
    for(i=3 ; i<=N ; i++) {
        while(Usize>=2 && turn(Up[Usize-1],Up[Usize],i)>=0) Usize--;
        Up[++Usize]=i;
        while(Dsize>=2 && turn(Down[Dsize-1],Down[Dsize],i)<=0) Dsize--;
        Down[++Dsize]=i;
    }
    for(i=2 ; i<=Usize ; i++) Res+=sqrt((A[Up[i]].x-A[Up[i-1]].x)*(A[Up[i]].x-A[Up[i-1]].x)+(A[Up[i]].y-A[Up[i-1]].y)*(A[Up[i]].y-A[Up[i-1]].y));
    for(i=2 ; i<=Dsize ; i++) Res+=sqrt((A[Down[i]].x-A[Down[i-1]].x)*(A[Down[i]].x-A[Down[i-1]].x)+(A[Down[i]].y-A[Down[i-1]].y)*(A[Down[i]].y-A[Down[i-1]].y));
    Res+=2*Pi*R;
    printf("%.12lf",Res);

    return 0;
}

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1128 KB Output is correct
2 Correct 0 ms 1128 KB Output is correct
3 Correct 0 ms 1128 KB Output is correct
4 Correct 0 ms 1128 KB Output is correct
5 Correct 0 ms 1128 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1128 KB Output is correct
2 Correct 0 ms 1128 KB Output is correct
3 Correct 0 ms 1128 KB Output is correct
4 Correct 0 ms 1128 KB Output is correct
5 Correct 0 ms 1128 KB Output is correct
6 Correct 0 ms 1128 KB Output is correct
7 Correct 0 ms 1128 KB Output is correct
8 Correct 0 ms 1128 KB Output is correct
9 Correct 0 ms 1128 KB Output is correct
10 Correct 0 ms 1128 KB Output is correct
11 Correct 0 ms 1128 KB Output is correct
12 Correct 0 ms 1128 KB Output is correct
13 Correct 0 ms 1128 KB Output is correct
14 Correct 0 ms 1128 KB Output is correct
15 Correct 0 ms 1128 KB Output is correct
16 Correct 0 ms 1128 KB Output is correct
17 Correct 0 ms 1128 KB Output is correct
18 Correct 0 ms 1128 KB Output is correct
19 Correct 0 ms 1128 KB Output is correct
20 Correct 0 ms 1128 KB Output is correct