/home/toolbox/public_html/solutions/108/10803/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
15 /*
16 * Author: Isaac Traxler
17 * Date: 2015-04-22
18 * Purpose:
19 * Problem: 10803
20 */
21
22 /*
23 * This template reads data until a terminating value is reached.
24 */
25
26 #define MAX_TOWNS 102
27 #define INFINITY 1000000
28 #define X 0
29 #define Y 1
30 #define BIG 100000
31
32 double a[MAX_TOWNS][MAX_TOWNS];
33 int towns[MAX_TOWNS][2];
34 int townCnt;
35 int caseNum = 0;
36 int numCases;
37
38 void init()
39 {
40 /* FUNCTION init */
41 int i;
42 int j;
43
44 for (i=0; i<MAX_TOWNS; i++)
45 {
46 /* for i */
47 for (j=0; j<MAX_TOWNS; j++)
48 {
49 /* for j */
50 a[i][j] = INFINITY;
51 } /* for j */
52 a[i][i] = 0; /* set digonal to distance 0 */
53 } /* for i */
54 } /* FUNCTION init */
55
56 void dump(char t[])
57 {
58 /* FUNCTION dump */
59 int i;
60 int j;
61
62 printf("%s\n", t);
63 for (i=0; i<townCnt; i++)
64 {
65 /* for i */
66 printf("%2d:", i);
67 for (j=0; j<townCnt; j++)
68 {
69 /* for j */
70 printf(" %13.4f", a[i][j]);
71 } /* for j */
72 printf("\n");
73 } /* for i */
74 printf("\n");
75 } /* FUNCTION dump */
76
77 void adjust()
78 {
79 /* FUNCTION adjust */
80 int i;
81 int j;
82
83 for (i=0; i<townCnt; i++)
84 {
85 /* for i */
86 for (j=0; j<townCnt; j++)
87 {
88 /* for j */
89 if (INFINITY != a[i][j])
90 {
91 /* if */
92 a[i][j] = BIG - a[i][j];
93 } /* if */
94 } /* for j */
95 } /* for i */
96 } /* FUNCTION adjust */
97
98 double findMax()
99 {
100 /* FUNCTION findMax */
101 int i;
102 int j;
103 double mx = -1;
104
105 for (i=0; i<townCnt; i++)
106 {
107 /* for i */
108 for (j=0; j<townCnt; j++)
109 {
110 /* for j */
111 if (INFINITY != a[i][j])
112 if (mx < a[i][j])
113 mx = a[i][j];
114 } /* for j */
115 } /* for i */
116 return mx;
117 } /* FUNCTION findMax */
118
119 void getInput()
120 {
121 /* FUNCTION getInput */
122 int i;
123
124 scanf(" %d ", &townCnt);
125 for (i=0; i<townCnt; i++)
126 {
127 /* for each town */
128 scanf(" %d %d ", &towns[i][X], &towns[i][Y]);
129 } /* for each town */
130 } /* FUNCTION getInput */
131
132 void buildAdjaencyMatrix()
133 {
134 /* FUNCTION buildAdjaencyMatrix */
135 int i;
136 int j;
137 int tmpx;
138 int tmpy;
139 int tmp;
140
141 for (i=0; i<townCnt; i++)
142 {
143 /* for each town */
144 for (j=i+1; j<townCnt; j++)
145 {
146 /* for each other town */
147 tmpx = towns[i][X] - towns[j][X];
148 tmpx = tmpx * tmpx;
149 tmpy = towns[i][Y] - towns[j][Y];
150 tmpy = tmpy * tmpy;
151 tmp = tmpx + tmpy;
152 printf("i=%d j=%d tmpx=%d tmpy=%d tmp=%d\n", i, j, tmpx, tmpy, tmp);
153 if (100 >= tmp)
154 {
155 /* towns are close enough to have a road */
156 a[i][j] = BIG - sqrt( (double) tmp);
157 a[j][i] = a[i][j];
158 } /* towns are close enough to have a road */
159 } /* for each other town */
160 } /* for each town */
161 } /* FUNCTION buildAdjaencyMatrix */
162
163 void fw()
164 {
165 /* FUNCTION fw */
166 int i;
167 int j;
168 int k;
169
170 for (k=1; k<townCnt; k++)
171 {
172 /* for k */
173 for (i=1; i<townCnt; i++)
174 {
175 /* for i */
176 for (j=1; j<townCnt; j++)
177 {
178 /* for j */
179 if ((a[i][k] + a[k][j]) < a[i][j])
180 {
181 /* k is a better way to get from i to j */
182 a[i][j] = a[i][k] + a[k][j];
183 } /* k is a better way to get from i to j */
184 } /* for j */
185 } /* for i */
186 } /* for k */
187 } /* FUNCTION fw */
188
189 void process()
190 {
191 /* FUNCTION process */
192 int total;
193 int i;
194 double mx;
195
196 init();
197 dump("Before");
198 buildAdjaencyMatrix();
199 dump("mid");
200 fw();
201 dump("After");
202 adjust();
203 dump("Last");
204 mx = findMax();
205 if (-1 != mx)
206 {
207 /* if */
208 printf("%.4f\n", mx);
209 } /* if */
210 else
211 {
212 /* else */
213 printf("Send Kurdy\n");
214 } /* else */
215 printf("\n");
216 } /* FUNCTION process */
217
218 int main()
219 {
220 /* main */
221 int i;
222 int numCases;
223
224 scanf(" %d ", &numCases);
225 for (i=1; i<=numCases; i++)
226 {
227 /* for */
228 printf("Case #%d:\n", i);
229 getInput();
230 process();
231 printf("\n");
232 } /* for */
233
234 return EXIT_SUCCESS;
235 } /* main */
236