#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 = ch.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 = ch[i];
point & le = ch[(i - 1 + n) % n];
point & ri = ch[(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;
}
| # |
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 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
1816 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
