## 11406 - Best Trap

Moderator: Board moderators

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

### 11406 - Best Trap

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
and is there any use of the N?

kiha
New poster
Posts: 37
Joined: Sat Dec 20, 2003 10:59 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
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

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York
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
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
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
Contact:
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

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.