Submission #13757

#	Time	Username	Problem	Language	Result	Execution time	Memory
13757		baneling100	Wall construction (kriii2_WA)	C++98	4 / 4	0 ms	1128 KiB

WA

#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 / 1
• Subtask 2: 3 / 3