## 11168 - Airport

**Moderator:** Board moderators

### 11168 - Airport

Hello. The issue: TLE . This is my algorithm:

- Get Convex hull.

- Form lines using each consecutive pair of points in the convex hull and calculate average distance

- Get min of that.

I guess that the issue lies in calculating the average distance so many times... Any ideas?

- Get Convex hull.

- Form lines using each consecutive pair of points in the convex hull and calculate average distance

- Get min of that.

I guess that the issue lies in calculating the average distance so many times... Any ideas?

But well, I am gonna research until I find a way to calculate the average distance in O(1) but until that, does anybody have tricky I/O cases he would want to share?

Edit: median won't even work for the sample I/O

Edit: I am currently looking for cases in which the average point thing would fail, whatever I try will work correctly in my program.

Edit: Nevermind, I got it.

Is there tricky I/O? Might because of precision problem, or some flow in my convex hull algorithm..

Could someone verify my I/O? Also, any tricky testcase will help me.

**Input:**

http://lilii.hp.infoseek.co.jp/air.in

**Output:**

Code: Select all

```
Case #1: 157.362
Case #2: 3.237
Case #3: 375.459
Case #4: 34.125
Case #5: 243.338
Case #6: 451.412
```

Code: Select all

```
Case #1: 78903.722
Case #2: 77266.451
Case #3: 78024.986
Case #4: 77425.874
Case #5: 77151.380
Case #6: 77910.437
```

What output do you get for the input generated by:?

Code: Select all

```
int main()
{
printf("1\n10000\n");
int i=0;
while (i<10000)
{
int j=80000-(i %6);
printf("%d %d\n",j,80000-(i++));
}
return 0;
}
```

Edit: I just tested my convex hull implementation on problem 681 so it is unlikelly that's the problem.

Code: Select all

```
6
1 1
1 1
1 1
1 2
1 2
2 2
```

I don't know what to tell you, other than having less than 3 points, as sclo pointed out, there shouldn't be any special cases. Maybe you don't print something right (you diffed the output?).

It was a very silly thing indeed.

Turns out that in some place I was doing printf("%0.3lf",0); as a rushed modiffication to handle some special cases.

But 0 is not a double, it is an integer, so the code was actually undefined, it could pretty much generate random numbers depending on the situation.

I was not able to find this before because the special cases were just in the input after some cases that already returned 0.000 , so the random bytes were assigned to zero.

But there it is.