11406  Best Trap
Moderator: Board moderators

 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!
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!

 New poster
 Posts: 10
 Joined: Sun Jan 20, 2008 8:19 am
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
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
Code: Select all
100 10 3
0 0
0 1
49 49
kiha

 New poster
 Posts: 10
 Joined: Sun Jan 20, 2008 8:19 am
did you AC it? how to solvekiha 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 inputI 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 hardCode: Select all
100 10 3 0 0 0 1 49 49
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.
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.

 New poster
 Posts: 10
 Joined: Sun Jan 20, 2008 8:19 am
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.crackerwang wrote:I still WA!!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.
is there any trick? or maybe my agorithm is wrong?
can you give me any hints?
THX!!
A special case is when there is only 1 point in the entire room.
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.
who can give me some i/o? I got wa and wa on this problem.