Submission #9033

#	Time	Username	Problem	Language	Result	Execution time	Memory
9033		veckal	Wall construction (kriii2_WA)	C++14	4 / 4	0 ms	1220 KiB

WA

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