oj.uz

Submission #10064

# Submission time Handle Problem Language Result Execution time Memory
10064 2014-10-04T02:03:18 Z veckal Wall construction (kriii2_WA) C++14
4 / 4
 0 ms 1256 KB 
#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.0 / 1.0

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

Subtask #2
3.0 / 3.0

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