oj.uz

Submission #9033

# Submission time Handle Problem Language Result Execution time Memory
9033 2014-09-27T10:52:37 Z veckal Wall construction (kriii2_WA) C++14
4 / 4
 0 ms 1220 KB 
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const double PI = acos(0.0)*2;
typedef pair<int, int> point;
#define X first
#define Y second

int n, r;
vector<point> points;

int ccw(point p, point a, point b) {
	point u(a.X-p.X, a.Y-p.Y), v(b.X-p.X, b.Y-p.Y);
	return u.X * v.Y - u.Y * v.X;
}

double dist(point a, point b) {
	return hypot(a.X-b.X, a.Y-b.Y);
}

int main() {
	scanf("%d%d", &n, &r);
	for (int i=0; i<n; ++i) {
		int x, y;
		scanf("%d%d", &x, &y);
		points.emplace_back(x, y);
	}
	point pivot = *min_element(points.begin(), points.end());
	vector<point> hull;
	hull.push_back(pivot);
	double ans = 0;
	while(1) {
		point ph = hull.back(), next = points[0];
		for (int i=1; i<points.size(); ++i) {
			int cross = ccw(ph, next, points[i]);
			if (cross > 0 || (cross == 0 && dist(next, ph) < dist(points[i], ph)))
				next = points[i];
		}
		ans += dist(ph, next);
		if (next == pivot) break;
		hull.push_back(next);
	}
	ans += 2*PI*r;
	printf("%.10f\n", ans);
	return 0;
}

Subtask #1
1.0 / 1.0

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

Subtask #2
3.0 / 3.0

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