11406 - Best Trap

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

Moderator: Board moderators

Post Reply
crackerwang
New poster
Posts: 10
Joined: Sun Jan 20, 2008 8:19 am

11406 - Best Trap

Post by crackerwang » Mon Feb 25, 2008 2:33 pm

I think that: if the answr is m, so there must be a circle who's radius is smaller than r and there are three or 2 point on it,and m point on or in it.
in the condion of 2 point the center of the circle is the mid of the 2 point

is above right?
but i got a WA?somebody help!

crackerwang
New poster
Posts: 10
Joined: Sun Jan 20, 2008 8:19 am

Post by crackerwang » Mon Feb 25, 2008 2:40 pm

and is there any use of the N?

kiha
New poster
Posts: 37
Joined: Sat Dec 20, 2003 10:59 pm

Post by kiha » Sat Mar 01, 2008 3:18 pm

There must be. I also first assumed that the result is regardless of N, and I got WA. Notice that the net is conical, so I think you can place it only so that it is wholly included in the room. Consider the input

Code: Select all

100 10 3
0 0
0 1
49 49
I presume the result to be 2, since no way you can cover the point (49, 49) with the circle of radius 10 if it has to be wholly inside the room. This one seems hard ;)
kiha

crackerwang
New poster
Posts: 10
Joined: Sun Jan 20, 2008 8:19 am

Post by crackerwang » Mon Mar 03, 2008 7:22 am

kiha wrote:There must be. I also first assumed that the result is regardless of N, and I got WA. Notice that the net is conical, so I think you can place it only so that it is wholly included in the room. Consider the input

Code: Select all

100 10 3
0 0
0 1
49 49
I presume the result to be 2, since no way you can cover the point (49, 49) with the circle of radius 10 if it has to be wholly inside the room. This one seems hard ;)
did you AC it? how to solve

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Post by sohel » Mon Mar 03, 2008 2:02 pm

There is no use of N. I first got WA when I considered that the cone has to be strictly inside the room. But later commenting out that part, the code got AC.

baodog
Experienced poster
Posts: 202
Joined: Wed Jul 04, 2007 6:53 am

Post by baodog » Sat Mar 08, 2008 5:37 am

That's just the result of a weak dataset. The cone has to be inside the room, but the dataset does not test it properly. I think the reason you might have got WA the first time is that your algorithm is not correct, i.e., it missed a way to put the cone in while keeping the cone inside the room.

http://www.programmingforfun.com/Progra ... points.htm

The more interesting problem is finding the smallest circle covering
a number of points. It's a well studied problem.

crackerwang
New poster
Posts: 10
Joined: Sun Jan 20, 2008 8:19 am

Post by crackerwang » Thu Mar 13, 2008 4:19 pm

sohel wrote:There is no use of N. I first got WA when I considered that the cone has to be strictly inside the room. But later commenting out that part, the code got AC.
I still WA!!
is there any trick? or maybe my agorithm is wrong?
can you give me any hints?
THX!!

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

Post by sclo » Fri Mar 21, 2008 1:16 pm

crackerwang wrote:
sohel wrote:There is no use of N. I first got WA when I considered that the cone has to be strictly inside the room. But later commenting out that part, the code got AC.
I still WA!!
is there any trick? or maybe my agorithm is wrong?
can you give me any hints?
THX!!
Suppose we don't care about N, then the circle can be always determined by 2 points. If we care about N, circle can be also determined by either 2 sides, or 1 side + 1 point.

A special case is when there is only 1 point in the entire room.

mysword
New poster
Posts: 26
Joined: Sun Mar 06, 2005 8:52 am

Re: 11406 - Best Trap

Post by mysword » Sat Apr 18, 2009 9:34 am

one question is that, will be size of room, N, be an integer or float number?
who can give me some i/o? I got wa and wa on this problem.

Post Reply

Return to “Volume 114 (11400-11499)”