oj.uz

Submission #9098

# Submission time Handle Problem Language Result Execution time Memory
9098 2014-09-27T11:59:39 Z mrcamel Wall construction (kriii2_WA) C++
4 / 4
 0 ms 1904 KB 
#include <cstdio>
#include <iostream>
#include <fstream>
#include <deque>
#include <algorithm>
#include <utility>
#include <vector>
#include <cmath>
#include <queue>
using namespace std;

#define in cin
#define out cout
#define PII pair<int, int>
#define x first
#define y second
#define pi 3.14159265358979323846

struct p
{
    double x, y;
    bool operator <(const p &pa) const {
        return (x < pa.x) || (x == pa.x && y < pa.y);
    }
};

double cross(const p &O, const p &A, const p &B)
{
    return (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x);
}

vector<p> ch(vector<p> P)
{
    int n = P.size(), k = 0;
    vector<p> H(2*n);

    sort(P.begin(), P.end());

    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];
    }

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

double getdistance(const p &a, const p &b)
{
    return sqrt( (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y) );
}

int main()
{
    //freopen("in.txt", "r+", stdin);

    int n; in >> n;
    double radi; in >> radi;

    out << fixed;
    out.precision(15);

    vector<p> pts;
    for(int i=0; i<n; i++)
    {
        p t; in >> t.x >> t.y;
        pts.push_back(t);
    }

    pts = ch(pts);

    if(n == 2)
    {
        out << getdistance(pts[0], pts[1]) * 2 + radi*2*pi;
        return 0;
    }

    double res = 0;
    int lenp = pts.size()-1;
    for(int i=0; i<lenp; i++)
    {
        int a = i-1; if(a < 0) a = lenp-1;
        int b = i;
        int c = i+1; if(b >= lenp) c = 0;

        p pa = pts[a];
        p pb = pts[b];
        p pc = pts[c];

        res += getdistance(pa, pb);

        double tan_ab = atan2(pb.y-pa.y, pb.x-pa.x);
        double tan_bc = atan2(pc.y-pb.y, pc.x-pb.x);

        if(tan_ab < 0) tan_ab += 2*pi;
        if(tan_bc < 0) tan_bc += 2*pi;

        double angle = abs(tan_ab - tan_bc);
        if(angle > pi) angle = 2*pi - angle;

        //out << angle << endl;
        res += radi*angle;
    }

    out << res << endl;

    return 0;
}

Subtask #1
1.0 / 1.0

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

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1904 KB Output is correct
2 Correct 0 ms 1904 KB Output is correct
3 Correct 0 ms 1904 KB Output is correct
4 Correct 0 ms 1904 KB Output is correct
5 Correct 0 ms 1904 KB Output is correct
6 Correct 0 ms 1904 KB Output is correct
7 Correct 0 ms 1904 KB Output is correct
8 Correct 0 ms 1904 KB Output is correct
9 Correct 0 ms 1904 KB Output is correct
10 Correct 0 ms 1904 KB Output is correct
11 Correct 0 ms 1904 KB Output is correct
12 Correct 0 ms 1904 KB Output is correct
13 Correct 0 ms 1904 KB Output is correct
14 Correct 0 ms 1904 KB Output is correct
15 Correct 0 ms 1904 KB Output is correct
16 Correct 0 ms 1904 KB Output is correct
17 Correct 0 ms 1904 KB Output is correct
18 Correct 0 ms 1904 KB Output is correct
19 Correct 0 ms 1904 KB Output is correct
20 Correct 0 ms 1904 KB Output is correct