Submission #9033

#TimeUsernameProblemLanguageResultExecution timeMemory
9033veckalWall construction (kriii2_WA)C++14
4 / 4
0 ms1220 KiB
#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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...