답안 #9101

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
9101	2014-09-27T12:02:45 Z	battery	Wall construction (kriii2_WA)	C++	1 / 4	0 ms	1256 KB

WA

#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);
    }

    vector<Point> 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);

    if (n == 2)
        distance += 2 * acos(-1.0) * (r);

    printf("%0.8Lf\n", distance);
    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	Incorrect	0 ms	1256 KB	Output isn't correct
2	Halted	0 ms	0 KB	-