/home/toolbox/public_html/solutions/102/10245/c.c
1 #include <stdio.h>
2 #include <string.h>
3 #include <sys/types.h>
4 #include <sys/stat.h>
5 #include <fcntl.h>
6 #include <stdint.h>
7 #include <math.h>
8 #include <stdlib.h>
9
10 #define TRUE (1 == 1)
11 #define FALSE (1 != 1)
12
13 #define DEBUG if (FALSE)
14 #define DEBUG1 if (FALSE)
15
16 #define MAXPOINTS 10005
17 #define MAXINT 0x7FFFFFFF
18
19 #define MIN(a,b) (((a)<(b))?(a):(b))
20
21 struct pointStruct
22 {
23 /* STRUCT pointStruct */
24 double x;
25 double y;
26 }; /* STRUCT pointStruct */
27
28
29 int numPoints;
30 struct pointStruct pts[MAXPOINTS];
31
32 /*
33 * Author: Isaac Traxler
34 * Date: 2014 11 6
35 * Purpose: fun -- implement divide and conquer
36 * Problem: 10245 - The Closest Pair
37 */
38
39 void dump()
40 {
41 /* FUNCTION dump */
42 int i;
43
44 printf("dump\n");
45 printf("NumPoints=%d\n", numPoints);
46 for (i=0; i<numPoints; i++)
47 {
48 /* for */
49 printf("point %d: (%lf, %lf)\n", i, pts[i].x, pts[i].y);
50 } /* for */
51 printf("\n\n");
52 } /* FUNCTION dump */
53
54 int compare(const void *a, const void *b)
55 {
56 /* FUNCTION compare */
57 struct pointStruct *p1 = a;
58 struct pointStruct *p2 = b;
59 int ret;
60
61 ret = p1->x - p2->x;
62 if (0 == ret)
63 {
64 /* Xs match, sort by y */
65 ret = p1->y - p2->y;
66 } /* Xs match, sort by y */
67
68 return ret;
69 } /* FUNCTION compare */
70
71 int getInput()
72 {
73 /* FUNCTION getInput */
74 int dataReadFlag;
75 int i;
76
77 dataReadFlag = FALSE;
78 scanf("%d ", &numPoints);
79 if (0 < numPoints)
80 {
81 /* then */
82 dataReadFlag = TRUE;
83 for (i=0; i<numPoints; i++)
84 {
85 /* for */
86 scanf("%lf %lf ", &pts[i].x, &pts[i].y);
87 } /* for */
88 qsort(pts, numPoints, sizeof(struct pointStruct), compare);
89 } /* then */
90
91 return (dataReadFlag);
92 } /* FUNCTION getInput */
93
94 double dist(struct pointStruct p1, struct pointStruct p2)
95 {
96 /* FUNCTION dist */
97 double x;
98 double y;
99
100 x = p1.x - p2.x;
101 y = p1.y - p2.y;
102 return (x * x + y * y);
103 } /* FUNCTION dist */
104
105 double divideAndConquer(int first, int last)
106 {
107 /* FUNCTION divideAndConquer */
108 /* if 3 or fewer left -- just do it
109 otherwise, split and do it again */
110 double ret;
111 double d1;
112 double d2;
113 double d3;
114 int i;
115
116 DEBUG printf("divideAndConquer: %d %d\n", first, last);
117 switch (last - first)
118 {
119 /* deal with possible number of points */
120 case 0:
121 ret = -1.0;
122 break;
123 case 1:
124 ret = dist(pts[first], pts[last]);
125 DEBUG printf("case 1: %lf\n", ret);
126 break;
127 case 2:
128 {
129 /* 3 points */
130 /*
131 d1 = divideAndConquer(first, first + 1);
132 d2 = divideAndConquer(first+1, last);
133 ret = MIN(d1, d2);
134 */
135 ret = MIN(divideAndConquer(first, first+1), divideAndConquer(first+1, last));
136 DEBUG printf("case 2: %lf (%lf %lf)\n", ret, d1, d2);
137 } /* 3 points */
138 break;
139 default: /* lots of points */
140 {
141 /* lots of points left -- divide them up again */
142 i = ( last - first) / 2;
143 /*
144 ret = MIN(divideAndConquer(first, first + i), divideAndConquer(first+i+1, last));
145 */
146
147 d1 = divideAndConquer(first, first + i);
148 d2 = divideAndConquer(first+i+1, last);
149 ret = MIN(d1, d2);
150 DEBUG printf("case default: %lf (%lf %lf)\n", ret, d1, d2);
151 } /* lots of points left -- divide them up again */
152 } /* deal with possible number of points */
153
154 DEBUG printf("divideAndConquer exit: %d %d\n", first, last);
155 return ret;
156 } /* FUNCTION divideAndConquer */
157
158 double calcDelta(double x)
159 {
160 /* FUNCTION calcDelta */
161 int i;
162 int j;
163 double delta;
164 double delta2;
165 double tmp;
166
167 delta = sqrt(x);
168 delta2 = x;
169 for (i=0; (numPoints-1) > i; i++)
170 {
171 /* for each initial point */
172 DEBUG printf("i=%d\n", i);
173 for (j=i+1; (j<numPoints); j++)
174 {
175 /* check every other point to the tight within delta */
176 tmp = pts[j].x - pts[i].x;
177 DEBUG printf("j loop: %lf i %d:(%lf, %lf) - j %d:(%lf, %lf)\n", tmp, i, pts[i].x, pts[i].y, j, pts[j].x, pts[j].y);
178 if (tmp > delta)
179 {
180 /* bail out */
181 DEBUG printf("bail at %d\n", j);
182 j = numPoints;
183 } /* bail out */
184 else
185 {
186 /* possible points */
187 tmp = dist(pts[i], pts[j]);
188 DEBUG printf("delta(%lf^2=%lf): %lf %d:(%lf, %lf) - %d:(%lf, %lf)\n", delta, delta2, tmp, i, pts[i].x, pts[i].y, j, pts[j].x, pts[j].y);
189 if (tmp < delta2)
190 {
191 /* new low */
192 delta2 = tmp;
193 delta = sqrt(tmp);
194 DEBUG printf("new %lf^2=%lf\n", delta, delta2);
195 } /* new low */
196 } /* possible points */
197 } /* check every other point to the tight within delta */
198 } /* for each initial point */
199 return delta;
200 } /* FUNCTION calcDelta */
201
202 void process()
203 {
204 /* FUNCTION process */
205 double d2;
206 double delta;
207
208 DEBUG1 dump();
209
210 if (1 < numPoints)
211 {
212 /* have at least two points */
213 d2 = divideAndConquer(0, numPoints-1);
214 delta = calcDelta(d2);
215
216 DEBUG printf("squared=%lf %lf delta: %lf\n", d2, sqrt(d2), delta);
217
218 if (((double) 10000.0) > delta)
219 {
220 /* then */
221 printf("%.4lf\n", delta);
222 } /* then */
223 else
224 {
225 /* else */
226 printf("INFINITY\n");
227 } /* else */
228 } /* have at least two points */
229 else
230 printf("INFINITY\n");
231 } /* FUNCTION process */
232
233 int main ()
234 {
235 /* main */
236 int moreToDo;
237
238 moreToDo = getInput();
239 while (moreToDo)
240 {
241 /* while */
242 process();
243 moreToDo = getInput();
244 } /* while */
245
246 return EXIT_SUCCESS;
247 } /* main */
248
249
250