Submission #10064

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

WA

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const double PI = acos(-1);
typedef pair<int, int> point;
#define X first
#define Y second

int n, r;
vector<point> points;

long long ccw(point a, point b, point c) {
	b.first -= a.first; b.second -= a.second;
	c.first -= a.first; c.second -= a.second;
	return b.first * (long long)c.second - c.first * (long long)b.second;
}

vector<point> convexHull(vector<point> dat) {
	vector<point> upper, lower;
	sort(dat.begin(), dat.end());
	for(int i = 0; i < dat.size(); i++) {
		while(upper.size() >= 2 && ccw(*++upper.rbegin(),*upper.rbegin(),dat[i]) >= 0) upper.pop_back();
		while(lower.size() >= 2 && ccw(*++lower.rbegin(),*lower.rbegin(),dat[i]) <= 0) lower.pop_back();
		upper.emplace_back(dat[i]);
		lower.emplace_back(dat[i]);
	}
	upper.insert(upper.end(), ++lower.rbegin(), --lower.rend());
	return upper;
}

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);
	}
	auto hull = convexHull(points);
	double ans = dist(hull[0], hull[hull.size()-1]);
	for (int i=1; i<hull.size(); ++i)
		ans += dist(hull[i], hull[i-1]);
	ans += 2*PI*r;
	printf("%.10f\n", ans);
	return 0;
}

• Subtask 1: 1 / 1
• Subtask 2: 3 / 3