/home/toolbox/public_html/solutions/102/10245/b.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 (TRUE)
14 #define DEBUG1 if (TRUE)
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 init()
40 {
41 /* FUNCTION init */
42 } /* FUNCTION init */
43
44 void dump()
45 {
46 /* FUNCTION dump */
47 int i;
48
49 printf("dump\n");
50 printf("NumPoints=%d\n", numPoints);
51 for (i=0; i<numPoints; i++)
52 {
53 /* for */
54 printf("point %d: (%lf, %lf)\n", i, pts[i].x, pts[i].y);
55 } /* for */
56 printf("\n\n");
57 } /* FUNCTION dump */
58
59 int compare(const void *a, const void *b)
60 {
61 /* FUNCTION compare */
62 struct pointStruct *p1 = a;
63 struct pointStruct *p2 = b;
64 int ret;
65
66 ret = p1->x - p2->x;
67 if (0 == ret)
68 {
69 /* Xs match, sort by y */
70 ret = p1->y - p2->y;
71 } /* Xs match, sort by y */
72
73 return ret;
74 } /* FUNCTION compare */
75
76 int getInput()
77 {
78 /* FUNCTION getInput */
79 int dataReadFlag;
80 int i;
81
82 dataReadFlag = FALSE;
83 scanf("%d ", &numPoints);
84 if (0 < numPoints)
85 {
86 /* then */
87 dataReadFlag = TRUE;
88 for (i=0; i<numPoints; i++)
89 {
90 /* for */
91 scanf("%lf %lf ", &pts[i].x, &pts[i].y);
92 } /* for */
93 qsort(pts, numPoints, sizeof(struct pointStruct), compare);
94 } /* then */
95
96 return (dataReadFlag);
97 } /* FUNCTION getInput */
98
99 double dist(struct pointStruct p1, struct pointStruct p2)
100 {
101 /* FUNCTION dist */
102 double x;
103 double y;
104
105 x = p1.x - p2.x;
106 y = p1.y - p2.y;
107 return (x * x + y * y);
108 } /* FUNCTION dist */
109
110 double dandq(int first, int last)
111 {
112 /* FUNCTION dandq */
113 /* if 3 or fewer left -- just do it
114 otherwise, split and do it again */
115 double ret;
116 double d1;
117 double d2;
118 double d3;
119 int i;
120
121 DEBUG printf("dandq: %d %d\n", first, last);
122 switch (last - first)
123 {
124 /* deal with possible number of points */
125 case 0:
126 ret = -1.0;
127 break;
128 case 1:
129 ret = dist(pts[first], pts[last]);
130 break;
131 case 2:
132 {
133 /* 3 points */
134 d1 = dist(pts[first], pts[first+1]);
135 d2 = dist(pts[first], pts[last]);
136 d3 = dist(pts[first+1], pts[last]);
137 ret = MIN(MIN(d1, d2), MIN(MIN(d1, d3), MIN(d2, d3)));
138 } /* 3 points */
139 break;
140 default: /* lots of points */
141 {
142 /* lots of points left -- divide them up again */
143 i = ( last - first) / 2;
144 ret = MIN(dandq(first, first + i), dandq(first+i+1, last));
145 } /* lots of points left -- divide them up again */
146 } /* deal with possible number of points */
147
148 return ret;
149 } /* FUNCTION dandq */
150
151 void process()
152 {
153 /* FUNCTION process */
154 double d2;
155
156 DEBUG1 dump();
157
158 if (1 < numPoints)
159 {
160 /* have at least two points */
161 init();
162
163 d2 = dandq(0, numPoints-1);
164
165 printf("squared=%lf %lf\n", d2, sqrt(d2));
166 if (100000000 <= d2)
167 {
168 /* then */
169 printf("Infinity\n");
170 } /* then */
171 else
172 {
173 /* else */
174 printf("%.4lf\n", sqrt(d2));
175 } /* else */
176 } /* have at least two points */
177 else
178 printf("Infinity\n");
179 } /* FUNCTION process */
180
181 int main ()
182 {
183 /* main */
184 int moreToDo;
185
186 init();
187 moreToDo = getInput();
188 while (moreToDo)
189 {
190 /* while */
191 process();
192 moreToDo = getInput();
193 } /* while */
194
195 return EXIT_SUCCESS;
196 } /* main */
197
198
199