oj.uz

답안 #10062

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
10062 2014-10-04T01:54:58 Z veckal Wall construction (kriii2_WA) C++14
1 / 4
 0 ms 1256 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;

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.begin(), --lower.end());
	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

# 결과 실행 시간 메모리 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
0.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 1256 KB Output is correct
2 Incorrect 0 ms 1256 KB Output isn't correct
3 Halted 0 ms 0 KB -