11168 - Airport

[Vexorian]

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?

[krijger]

I don't want to give everything away, but you need to calculate the average distance to a line in O(1) time. Try to think of a way yourself.

[Vexorian]

Before reading your post, I tried with an average point. So I only had to get the line with the minimum distance to it and then get the average distance, it seems it did not work since I got WA... Might as well try with the median.

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.

[rio]

I find a way to calculate the average distance in O(1), but getting WA..
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

Thanks in advance.

[krijger]

My AC program gives the following:

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

[rio]

Thanks krijger.My code was overflowting..

ADD : fixed and got AC. Thanks.

[Vexorian]

My new algorithm is giving me WA, but it does krijger's output correctly so I am pretty much betting it is not a mistake with the algorithm but something silly.

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;
}

I get 2.500

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

[rio]

My AC code outputs 2.500 too.

[sclo]

Have you checked for special cases such as all points on a line or n<=2? I don't think there're any other special cases, assuming that your convex hull works properly. I'm not sure whether 2 houses can be arbitarily close to each other.

[Darko]

If two houses are arbitrarily close, then they have to be the same house - they have integer coordinates. I treated them as different ones for the average distance part, but I don't know if there is a such case in judge's data.

[Vexorian]

Thanks.

I forgot about the n=1 case. But still WA.

- Works when all points are in a line
- Works with n<3

Any other special cases?

[Darko]

Again, I don't know if there are such cases, but have you tried something like this?

Code: Select all

6
1 1
1 1
1 1
1 2
1 2
2 2

[Vexorian]

returns 0.167 which I think is the right answer.

[Darko]

Funny thing - my program crashes on that input (I never checked, I passed the wrong size to my convexHull()), so there are no duplicate points in judge's input, that's for sure.

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?).

[Vexorian]

Thanks for your help everyone.

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.