| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 9069 | battery | Wall construction (kriii2_WA) | C++98 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
typedef long double coord_t; // coordinate type
typedef long double coord2_t; // must be big enough to hold 2*max(|coordinate|)^2
struct Point {
coord_t x, y;
bool operator <(const Point &p) const {
return x < p.x || (x == p.x && y < p.y);
}
coord_t distance(const Point &p) const {
return sqrt((x - p.x) * (x - p.x) + (y - p.y) * (y - p.y));
}
};
coord_t angle(Point pointA, Point pointB, Point pointC)
{
coord_t a = pointB.x - pointA.x;
coord_t b = pointB.y - pointA.y;
coord_t c = pointB.x - pointC.x;
coord_t d = pointB.y - pointC.y;
coord_t atanA = atan2(a, b);
coord_t atanB = atan2(c, d);
return atanB - atanA;
}
// 2D cross product of OA and OB vectors, i.e. z-component of their 3D cross product.
// Returns a positive value, if OAB makes a counter-clockwise turn,
// negative for clockwise turn, and zero if the points are collinear.
coord2_t cross(const Point &O, const Point &A, const Point &B)
{
return (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x);
}
// Returns a list of points on the convex hull in counter-clockwise order.
// Note: the last point in the returned list is the same as the first one.
vector<Point> convex_hull(vector<Point> &P)
{
int n = P.size(), k = 0;
vector<Point> H(2*n);
// Sort points lexicographically
sort(P.begin(), P.end());
// Build lower hull
for (int i = 0; i < n; ++i) {
while (k >= 2 && cross(H[k-2], H[k-1], P[i]) <= 0) k--;
H[k++] = P[i];
}
// Build upper hull
for (int i = n-2, t = k+1; i >= 0; i--) {
while (k >= t && cross(H[k-2], H[k-1], P[i]) <= 0) k--;
H[k++] = P[i];
}
H.resize(k);
return H;
}
int n, r;
vector<Point> points;
int main(int argc, char** argv)
{
scanf("%d %d", &n, &r);
for (int i = 0; i < n; ++i)
{
Point p;
scanf("%Lf %Lf", &p.x, &p.y);
points.push_back(p);
}
auto answer = convex_hull(points);
coord_t distance = .0;
for (int i = 0; i < answer.size() - 1; ++i)
{
distance += answer[i].distance(answer[i+1]);
if (i > 0)
{
coord_t ang = angle(answer[i-1],answer[i], answer[i+1]);
while (ang < 0)
ang += 2 * acos(-1.0);
distance += (ang) / 2 / acos(-1.0) * 2 * acos(-1.0) * ((coord_t)r);
}
}
coord_t ang = angle(answer[answer.size() - 2],answer[0], answer[1]);
while (ang < 0)
ang += 2 * acos(-1.0);
distance += (ang) / 2 / acos(-1.0) * 2 * acos(-1.0) * ((coord_t)r);
printf("%0.12Lf\n", distance);
return 0;
}