Submission #9032

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
9032	2014-09-27T10:51:58 Z	wookayin	Wall construction (kriii2_WA)	C++14	1 / 4	0 ms	1816 KB

WA

#include <array>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <functional>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <iostream>
#include <sstream>
using namespace std;

struct point {
	int x, y;
};
bool operator < (const point &A, const point &B) {
	return make_pair(A.x, A.y) < make_pair(B.x, B.y);
}

typedef vector<point> polygon;

int ccw(const point &A, const point &B, const point &C) {
	int s = 0;
	s += A.x * B.y + B.x * C.y + C.x * A.y;
	s -= A.y * B.x + B.y * C.x + C.y * A.x;
	return s;
}

polygon convexHull(vector<point> a) {
	polygon u, l;
	sort(a.begin(), a.end()); // compare by x, and then by y
	for(const point &p : a) {
		while(u.size() >= 2 && ccw(u[u.size() - 2], u.back(), p) >= 0) u.pop_back();
		while(l.size() >= 2 && ccw(l[l.size() - 2], l.back(), p) <= 0) l.pop_back();
		u.push_back(p); l.push_back(p);
	}
	u.insert(u.end(), ++l.begin(), --l.end()); /* make into a complete polygon */
	return u;
}
double distance(point &a, point &b) {
	return hypot(a.x - b.x, a.y - b.y);
}

double getAngle(point &a, point &o, point &b) {
	double A = distance(a, o);
	double B = distance(b, o);
	double C = distance(a, b);

	return acos((A * A + B * B - C * C) / 2 * A * B);
}

double go(vector<point> &a, double r) {
	vector<point> ch = convexHull(a);
	int n = a.size();
	double L = 0;

	if(n == 2) {
		double d = distance( a[0], a[1] );
		return 2 * acos(0) * 2 * r + 2 * d;
	}

	for(int i = 0; i < n; ++ i) {
		point & me = a[i];
		point & le = a[(i - 1 + n) % n];
		point & ri = a[(i + 1 + n) % n];
		double angle = getAngle(le, me, ri);
		L += r * angle;
//		cout << r * angle << endl;

		// me ~ ri
		double d = distance(me, ri);
//		cout << d << endl;
		L += d;
	}

	return L;
}

int main() {
	int n, r;
	while(cin >> n >> r) {
		vector<point> a;
		for(int i=0; i<n; ++i) {
			int x, y; cin >> x >> y;
			a.push_back( { x, y } );
		}
		printf("%.11f\n", go(a, r));
	}
	return 0;
}

Subtask #1

1.0 / 1.0

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

Subtask #2

0.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	0 ms	1816 KB	Output isn't correct
2	Halted	0 ms	0 KB	-