মঙ্গলবার, ২০ অক্টোবর, ২০১৫

[Point,Line] Problem 1 : uva railway



Problem id : uva railway
The idea is to calculate closest point from pM for all line segments and then taking the minimum.







So,from the figure the answer would be
For all i (1 to n) //There are n line segments , so n closest points from pM
ans = cp_i so that di is minimum

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
#include <bits/stdc++.h>
#define loop(x) for(int a=0;a<x;a++)
#define INF 1e9
#define EPS 1e-9
using namespace std;
//Geometry Template for Points and Lines
struct point
{
    double x, y;   // only used if more precision is needed
    point()
    {
        x = y = 0.0;    // default constructor
    }
    point(double _x, double _y) : x(_x), y(_y) {}        // user-defined
    bool operator < (point other) const   // override less than operator
    {
        if (fabs(x - other.x) > EPS)                 // useful for sorting
            return x < other.x;          // first criteria , by x-coordinate // < min to max
        return y < other.y;
    }          // second criteria, by y-coordinate // < min to max

    // use EPS (1e-9) when testing equality of two floating points
    bool operator == (point other) const
    {
        return (fabs(x - other.x) < EPS && (fabs(y - other.y) < EPS));
    }
}; // 2 points have same x and y co-ordinate
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);
}
struct line
{
    double a, b, c;
};          // a way to represent a line

struct vec
{
    double x, y;  // name: `vec' is different from STL vector
    vec(double _x, double _y) : x(_x), y(_y) {}
};

vec toVec(point a, point b)         // convert 2 points to vector a->b  AB
{
    return vec(b.x - a.x, b.y - a.y);
} //same as thinking about a point w.r.t. origin

vec scale(vec v, double s)          // nonnegative s = [<1 .. 1 .. >1]
{
    return vec(v.x * s, v.y * s);
}               // shorter__same__longer

point translate(point p, vec v)          // translate p according to v
{
    return point(p.x + v.x , p.y + v.y);
}

double dot(vec a, vec b)
{
    return (a.x * b.x + a.y * b.y);
}

double norm_sq(vec v) //returns the value^2 of the vector
{
    return v.x * v.x + v.y * v.y;
}
// returns the distance from p to the line defined by
// two points a and b (a and b must be different)
// the closest point is stored in the 4th parameter (byref)
double distToLine(point p, point a, point b, point &c)
{
    // formula: c = a + u * ab
    vec ap = toVec(a, p), ab = toVec(a, b);
    double u = dot(ap, ab) / norm_sq(ab);
    c = translate(a, scale(ab, u));                  // translate a to c
    return dist(p, c);
}           // Euclidean distance between p and c

// returns the distance from p to the line segment ab defined by
// two points a and b (still OK if a == b)
// the closest point is stored in the 4th parameter (byref)
double distToLineSegment(point p, point a, point b, point &c)
{
    vec ap = toVec(a, p), ab = toVec(a, b);
    double u = dot(ap, ab) / norm_sq(ab);
    if (u < 0.0)
    {
        c = point(a.x, a.y);                   // closer to a
        return dist(p, a);
    }         // Euclidean distance between p and a
    if (u > 1.0)
    {
        c = point(b.x, b.y);                   // closer to b
        return dist(p, b);
    }         // Euclidean distance between p and b
    return distToLine(p, a, b, c);
}          // run distToLine as above

int main()
{
       double Xm,Ym;

    while(scanf("%lf %lf",&Xm,&Ym)==2)
    {

        int N;
        cin>>N;
        double prev_x,prev_y;
        cin>>prev_x>>prev_y;
        double min_dist = INF; ///init
        point P_close;
        loop(N)
        {
            double now_x,now_y;
            cin>>now_x>>now_y;
            point P_m(Xm,Ym);
            point P_a(prev_x,prev_y);
            point P_b(now_x,now_y);
            point P_c;
            ///Find closest distance for all line segments and take the minimum of them
            double temp_dist = distToLineSegment(P_m,P_a,P_b,P_c);
       //     cout<<"min:"<<min_dist<<" temp:"<<temp_dist<<endl;
            if(temp_dist<min_dist) 
            {
                min_dist = temp_dist; //This line is a must for comparison 
                P_close.x = P_c.x;
                P_close.y = P_c.y;
            }
            prev_x = now_x;
            prev_y = now_y;

        }
        printf("%.4lf\n",P_close.x); //4 decimal point
        printf("%.4lf\n",P_close.y);


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

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

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

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