oj.uz

Submission #8408

# Submission time Handle Problem Language Result Execution time Memory
8408 2014-09-13T17:11:17 Z ainta Wall construction (kriii2_WA) C++
4 / 4
 0 ms 1116 KB 
#include<stdio.h>
#include<algorithm>
#include<math.h>
using namespace std;
#define PI 3.14159265359
int n, R, st[1010], top, P[1010];
double Res;
struct point{
	int x, y;
	bool operator <(const point &p)const{
		return x != p.x ? x < p.x : y < p.y;
	}
}w[1010];
int ccw(point a, point b, point c){
	return (b.x - a.x)*(c.y - a.y) - (b.y - a.y)*(c.x - a.x);
}
double dist(point a, point b){
	double D = (b.x - a.x)*(b.x - a.x) + (b.y - a.y) * (b.y - a.y);
	return sqrt(D);
}
int main()
{
	int i, cnt = 0;
	scanf("%d%d", &n, &R);
	for (i = 0; i < n; i++){
		scanf("%d%d", &w[i].x, &w[i].y);
	}
	sort(w, w + n);
	st[++top] = 0;
	for (i = 1; i < n; i++){
		while (top > 1 && ccw(w[st[top - 1]], w[st[top]], w[i]) <= 0)top--;
		st[++top] = i;
	}
	for (i = 1; i < top; i++)P[++cnt] = st[i];
	top = 0;
	st[++top] = 0;
	for (i = 1; i < n; i++){
		while (top > 1 && ccw(w[st[top - 1]], w[st[top]], w[i]) >= 0)top--;
		st[++top] = i;
	}
	for (i = top; i > 1; i--)P[++cnt] = st[i];
	P[cnt + 1] = P[1];
	for (i = 1; i <= cnt; i++){
		Res += dist(w[P[i + 1]], w[P[i]]);
	}
	printf("%.11lf\n", Res + PI * 2.0 * R);
}

Subtask #1
1.0 / 1.0

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

Subtask #2
3.0 / 3.0

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