বুধবার, ২৮ অক্টোবর, ২০১৫

[Convex Hull] LightOJ 1239 - Convex Fence

Problem id : LOJ 1239

Think in terms of the trivial cases first.For n = 2 ,






For n = 3 ,





Can you guess the formula now?
l1 = dist(point 1,point 3)
l2 = dist(point 2,point 3)
l3 = dist(point 1,point 2)

And we can easily show that arc 1 + arc 2 + arc 3 make 360 degrees and as they are from the same circle .
The answer is sumof(li) + 2*PI*d

For n > 3 ,






So,the idea is to construct a convex hull from the points and find it's perimeter and add 2*PI*d to the answer , and done :-D


Code :



  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
// Implementation of Andrew's monotone chain 2D convex hull algorithm.
// Asymptotic complexity: O(n log n).
// Practical performance: 0.5-1.0 seconds for n=1000000 on a 1GHz machine.
#include<bits/stdc++.h>
using namespace std;
#define PI acos(-1.0) // important constant; alternative #define PI (2.0 * acos(0.0))
typedef double coord_t;         // coordinate type
typedef double coord2_t;  // must be big enough to hold 2*max(|coordinate|)^2

struct Point
{
    coord_t x, y;

    Point()
    {
        this->x = 0.0000000f;
        this->y = 0.0000000f;
    }
    Point(coord_t x,coord_t y)
    {

        this->x = x;
        this->y = y;

    }
    bool operator <(const Point &p) const
    {
        return x < p.x || (x == p.x && y < p.y);
    }

};
vector<Point>H_global;
double dist(Point p1, Point p2)                  // Euclidean distance
{
    // hypot(dx, dy) returns sqrt(dx * dx + dy * dy)
    return hypot(p1.x - p2.x, p1.y - p2.y);
}

// 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 (long)(A.x - O.x) * (B.y - O.y) - (long)(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.
void 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);
    for(int a=0; a<H.size(); a++)
        H_global.push_back(H[a]);


}
/*
//Implementation details
vector<Point>in;
Point p(-3.4,50);
Point p1(33.4,51);
Point p2(30.4,15);
Point p3(31.4,45);
Point p4(3.4,55);
Point p5(-33.4,15);
Point p6(-31.4,75);
in.push_back(p);
in.push_back(p1);
in.push_back(p2);
in.push_back(p3);
in.push_back(p4);
in.push_back(p5);
in.push_back(p6);

vector<Point>out = convex_hull(in);

for(int a=0;a<out.size();a++)
{
    Point pp = out[a];
    cout<<pp.x<<"  "<<pp.y<<endl;

}


*/
vector<Point>in;


int main()
{
    int T;
    int cas =0;
    scanf("%d",&T);
    while(T--)
    {
        int n,d;
        scanf("%d %d",&n,&d);
        while(n--)
        {
            coord_t x,y;
            cin>>x>>y;
            Point p(x,y);
            in.push_back(p);


        }

        convex_hull(in);
        vector<Point>    out_c_h(H_global.begin(),H_global.end());
        long double dist_sum = 0.000000000f;
        if(n==2)
        {
            dist_sum += 2*dist(in[0],in[1]);
        }
        else
            for(int a=0; a<out_c_h.size() - 1; a++)
            {
                dist_sum += dist(out_c_h[a],out_c_h[a+1]) ;
            }
        dist_sum += 2*PI*d;
        printf("Case %d: %Lf\n",++cas,dist_sum);
        out_c_h.clear();
        in.clear();
        H_global.clear();
    }


    return 0;
}
এর দ্বারা পোস্ট করা এই সময়ে

কোন মন্তব্য নেই:

একটি মন্তব্য পোস্ট করুন

এতে সদস্যতা: মন্তব্যগুলি পোস্ট করুন (Atom)