/home/toolbox/public_html/solutions/108/10803/a.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
31 double a[MAX_TOWNS][MAX_TOWNS];
32 int towns[MAX_TOWNS][2];
33 int townCnt;
34 int caseNum = 0;
35 int numCases;
36
37 void init()
38 {
39 /* FUNCTION init */
40 int i;
41 int j;
42
43 for (i=0; i<MAX_TOWNS; i++)
44 {
45 /* for i */
46 for (j=0; j<MAX_TOWNS; j++)
47 {
48 /* for j */
49 a[i][j] = INFINITY;
50 } /* for j */
51 a[i][i] = 0; /* set digonal to distance 0 */
52 } /* for i */
53 } /* FUNCTION init */
54
55 void dump(char t[])
56 {
57 /* FUNCTION dump */
58 int i;
59 int j;
60
61 printf("%s\n", t);
62 for (i=0; i<townCnt; i++)
63 {
64 /* for i */
65 printf("%2d:", i);
66 for (j=0; j<townCnt; j++)
67 {
68 /* for j */
69 printf(" %4.4f", a[i][j]);
70 } /* for j */
71 printf("\n");
72 } /* for i */
73 printf("\n");
74 } /* FUNCTION dump */
75
76 double findMax()
77 {
78 /* FUNCTION findMax */
79 int i;
80 int j;
81 double mx = INFINITY;
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 if (mx < a[i][j])
91 mx = a[i][j];
92 } /* for j */
93 } /* for i */
94 return mx;
95 } /* FUNCTION findMax */
96
97 void getInput()
98 {
99 /* FUNCTION getInput */
100 int i;
101
102 scanf(" %d ", &townCnt);
103 for (i=0; i<townCnt; i++)
104 {
105 /* for each town */
106 scanf(" %d %d ", &towns[i][X], &towns[i][Y]);
107 } /* for each town */
108 } /* FUNCTION getInput */
109
110 void buildAdjaencyMatrix()
111 {
112 /* FUNCTION buildAdjaencyMatrix */
113 int i;
114 int j;
115 int tmpx;
116 int tmpy;
117 int tmp;
118
119 for (i=0; i<townCnt; i++)
120 {
121 /* for each town */
122 for (j=i+1; j<townCnt; j++)
123 {
124 /* for each other town */
125 tmpx = towns[i][X] - towns[j][X];
126 tmpx = tmpx * tmpx;
127 tmpy = towns[i][Y] - towns[j][Y];
128 tmpy = tmpy * tmpy;
129 tmp = tmpx + tmpy;
130 printf("i=%d j=%d tmpx=%d tmpy=%d tmp=%d\n", i, j, tmpx, tmpy, tmp);
131 if (100 >= tmp)
132 {
133 /* towns are close enough to have a road */
134 a[i][j] = sqrt( (double) tmp);
135 a[j][i] = a[i][j];
136 } /* towns are close enough to have a road */
137 } /* for each other town */
138 } /* for each town */
139 } /* FUNCTION buildAdjaencyMatrix */
140
141 void fw()
142 {
143 /* FUNCTION fw */
144 int i;
145 int j;
146 int k;
147
148 for (k=1; k<townCnt; k++)
149 {
150 /* for k */
151 for (i=1; i<townCnt; i++)
152 {
153 /* for i */
154 for (j=1; j<townCnt; j++)
155 {
156 /* for j */
157 if ((a[i][k] + a[k][j]) < a[i][j])
158 {
159 /* k is a better way to get from i to j */
160 a[i][j] = a[i][k] + a[k][j];
161 } /* k is a better way to get from i to j */
162 } /* for j */
163 } /* for i */
164 } /* for k */
165 } /* FUNCTION fw */
166
167 void process()
168 {
169 /* FUNCTION process */
170 int total;
171 int i;
172 double mx;
173
174 init();
175 dump("Before");
176 buildAdjaencyMatrix();
177 dump("mid");
178 fw();
179 dump("After");
180 mx = findMax();
181 if (-1 != mx)
182 {
183 /* if */
184 printf("%.4f\n", mx);
185 } /* if */
186 else
187 {
188 /* else */
189 printf("Send Kurdy\n");
190 } /* else */
191 printf("\n");
192 } /* FUNCTION process */
193
194 int main()
195 {
196 /* main */
197 int i;
198 int numCases;
199
200 scanf(" %d ", &numCases);
201 for (i=1; i<=numCases; i++)
202 {
203 /* for */
204 printf("Case #%d:\n", i);
205 getInput();
206 process();
207 printf("\n");
208 } /* for */
209
210 return EXIT_SUCCESS;
211 } /* main */
212