OJ Board

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?

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.

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.

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: Thanks in advance.

My AC program gives the following:

Thanks krijger.My code was overflowting..

ADD : fixed and got AC. Thanks.

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:?
I get 2.500

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

My AC code outputs 2.500 too.

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.

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.

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?

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

returns 0.167 which I think is the right answer.

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

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.