11406 - Best Trap

[crackerwang]

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]

and is there any use of the N?

[kiha]

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

[crackerwang]

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]

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]

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]

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]

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]

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.