11168 - Airport

All about problems in Volume 111. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Vexorian
Learning poster
Posts: 100
Joined: Sat Aug 26, 2006 5:50 am

11168 - Airport

Post by Vexorian » Mon Feb 19, 2007 8:05 pm

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
New poster
Posts: 39
Joined: Wed Jul 21, 2004 12:35 am

Post by krijger » Mon Feb 19, 2007 9:04 pm

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
Learning poster
Posts: 100
Joined: Sat Aug 26, 2006 5:50 am

Post by Vexorian » Tue Feb 20, 2007 12:48 am

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.

User avatar
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Post by rio » Tue Feb 20, 2007 1:03 pm

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
New poster
Posts: 39
Joined: Wed Jul 21, 2004 12:35 am

Post by krijger » Tue Feb 20, 2007 4:19 pm

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

User avatar
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Post by rio » Tue Feb 20, 2007 4:54 pm

Thanks krijger.My code was overflowting..

ADD : fixed and got AC. Thanks.

Vexorian
Learning poster
Posts: 100
Joined: Sat Aug 26, 2006 5:50 am

Post by Vexorian » Wed Feb 21, 2007 4:49 am

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.

User avatar
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Post by rio » Wed Feb 21, 2007 6:36 am

My AC code outputs 2.500 too.

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Wed Feb 21, 2007 9:36 pm

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
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko » Wed Feb 21, 2007 10:17 pm

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
Learning poster
Posts: 100
Joined: Sat Aug 26, 2006 5:50 am

Post by Vexorian » Wed Feb 21, 2007 10:19 pm

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
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko » Wed Feb 21, 2007 10:38 pm

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
Learning poster
Posts: 100
Joined: Sat Aug 26, 2006 5:50 am

Post by Vexorian » Wed Feb 21, 2007 11:38 pm

returns 0.167 which I think is the right answer.

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko » Thu Feb 22, 2007 12:51 am

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
Learning poster
Posts: 100
Joined: Sat Aug 26, 2006 5:50 am

Post by Vexorian » Thu Feb 22, 2007 6:19 am

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.

Post Reply

Return to “Volume 111 (11100-11199)”