/home/toolbox/public_html/solutions/102/10245/z.cpp
1 /*
2 * Luke Duncan
3 * CIS 306 - Discrete Math II
4 * Fall 2009
5 *
6 * Term Project Part 1
7 * UVa 10245 - The Closest Pair Problem
8 */
9
10
11 // HEADERS /////////////////////////////////////////////////////////
12 #include<iostream>
13 #include<vector>
14 #include<algorithm>
15 #include<cmath>
16 #include<cstdio>
17 using namespace std;
18
19
20 // DATA STRUCTURES /////////////////////////////////////////////////
21 struct point
22 {
23 double x;
24 double y;
25 };
26
27 double calcDistance(point p1, point p2);
28 void splitVector(vector<point> allPoints, vector<point> &left, vector<point> &right, int line);
29 double closestPairPlaneSweep(vector<point> allPoints, double delta);
30 double closestPair(vector<point> allPoints);
31
32 // CUSTOM SORTS ////////////////////////////////////////////////////
33 bool sortByX (point p1, point p2)
34 {
35 return (p1.x < p2.x);
36 }
37 bool sortByY (point p1, point p2)
38 {
39 return (p1.y < p2.y);
40 }
41 bool sortByXY (point p1, point p2)
42 {
43 if (p1.x == p2.x) return (p1.y < p2.y);
44 else return (p1.x < p2.x);
45 }
46
47 // CLOSEST PAIR ALGO'S /////////////////////////////////////////////
48 double calcDistance(point p1, point p2)
49 /*
50 * Pre: Two points are passed
51 * Post: The distance between them is calculated using Pathagorean Theorem
52 */
53 {
54 double a;
55 double b;
56
57 a = p1.x - p2.x;
58 b = p1.y - p2.y;
59
60 return sqrt(a*a + b*b);
61 }
62
63 void splitVector(vector<point> allPoints, vector<point> &left, vector<point> &right, int line)
64 /*
65 * Pre: A vector X is passed, with two empy vectors L and R
66 * Post: The left half of X is stored in L and the right in R.
67 */
68 {
69 for (int i=0; i<allPoints.size(); i++)
70 {
71 if (i<line) left.push_back(allPoints[i]);
72 else right.push_back(allPoints[i]);
73 }
74
75 }
76
77 double closestPairPlaneSweep(vector<point> allPoints, double delta)
78 /*
79 * Pre: A vector of points, sorted by Y-coordinates, is passed by Divide-and-Conquer
80 * algo
81 * Post: The shortest distance between any two points is returned as a double
82 */
83 {
84 for (int i=0; i<allPoints.size(); i++)
85 {
86 for (int j=i+1; j<allPoints.size() && (allPoints[j].y > (allPoints[i].y - delta)); j++)
87 // Check everything in front of the current point
88 // stoping when the Sweeping line is greater than delta away from the point
89 {
90 double curDelta = calcDistance(allPoints[i], allPoints[j]);
91 delta = min(delta, curDelta);
92 }
93 }
94 return delta;
95 }
96
97 double closestPair(vector<point> allPoints)
98 /*
99 * Pre: A vector of points, sorted by X-Coordinates, is passed
100 * Post: A Divide-and-Conquer closest pair algorithm calculates the
101 * the smallest distance between any two points. A double is returned
102 */
103 {
104 if (allPoints.size() == 1) return 10000;
105
106 int seperationLine = (allPoints.size())/2;
107 vector<point> left;
108 vector<point> right;
109 double deltaLeft;
110 double deltaRight;
111 double delta;
112 double deltaMid;
113 double deltaMidLeft;
114 double deltaMidRight;
115
116 splitVector(allPoints, left, right, seperationLine);
117 deltaLeft = closestPair(left);
118 deltaRight = closestPair(right);
119 delta = min(deltaLeft, deltaRight);
120
121 deltaMid = double(allPoints[seperationLine].x);
122 deltaMidLeft = deltaMid - delta;
123 deltaMidRight = deltaMid + delta;
124
125 while (!(allPoints[0].x >= deltaMidLeft && allPoints[0].x <= deltaMidRight))
126 // Delete everything to the left and not in delta
127 {
128 allPoints.erase(allPoints.begin());
129 }
130
131 while (!(allPoints[allPoints.size()-1].x >= deltaMidLeft && allPoints[allPoints.size()-1].x <= deltaMidRight))
132 // Delete everything to the right and not in delta
133 {
134 allPoints.erase(allPoints.end()-1);
135 }
136
137
138 sort(allPoints.begin(), allPoints.end(), sortByY);
139
140
141 return closestPairPlaneSweep(allPoints, delta);
142 }
143
144 // DRIVER //////////////////////////////////////////////////////////
145
146 int main()
147 /*
148 * Pre: The program is started
149 * Post: The program successfully computes the shortest distance for each graph
150 * for a pair of points
151 */
152 {
153 int N;
154
155 while (cin >> N && N)
156 {
157 vector<point> allPoints;
158 for (int i=0; i<N; i++)
159 {
160 point curPoint;
161 cin >> curPoint.x >> curPoint.y;
162 allPoints.push_back(curPoint);
163 }
164 sort(allPoints.begin(), allPoints.end(), sortByX);
165 double closest = closestPair(allPoints);
166 if (closest < 10000)
167 {
168 cout.precision(4);
169 cout << fixed << closest << endl;
170 }
171 else
172 {
173 cout << "INFINITY\n";
174 }
175 }
176
177 return 0;
178 }
179