I've no idea.Could anybody help me?

I have the same question.
I think if distances between all pairs of cities of chosen subset are less or equal to R then this subset can be destroyed. But i don't know how to find this subset quickly.

1. R = R - r;  Then You will solve problem with N points and a circle of radius R
2. Build 2 circles thru all pairs of points (it is n*(n-1) circles) and calculate amount of points in this circles. Maximum of them is the answer.

Sorry for my bad english :-)

Thank you first.
And I have a little question,why we can do the first step?

Edited by author 28.10.2004 20:50

I mean,you say first we can let R=R-r to make the cities become points.I don't know why we can do this.

Because city can be destroyed by djin only if
d+r<=R => d<=R-r (d - distance between center of city and djin).

Edited by author 29.10.2004 16:27

Thanks.

Are you sure?
Maybe I have not understood your solution properly, but what your solution does in case on 2 distant sets of cities. Each set can be destroyed by 1 bottle.

For example 4 cities.
0 0
1 1
100 100
101 101

And R = 3, r = 0;

Your solution would be 4, but it's, obviously, 2.

This means that I have not understood what you have written...

Then how do you process the case which I have presented?

Maybe it would be better to continue this conversation via e-mail?

Ok. my e-mail is  marilyn_manson@bk.ru

I think Vic right

sorry my bad English

One for center and one determines the length of the radius?

If so, then I am confused with your solution...

Edited by author 04.08.2006 23:52

Of course not! Both points are lying on the circle

Barinov jjot. Strange but it works since first submit! Thanks a lot!!!

Why 2 circles?
And what is the center of those circles?

2 points can make 2 circles with the exact R.
(from two different directions!)

I am also confused just know. :)

No.
For example there are 2 circles, which have points (-3; 0) and (3; 0) and R = 5: with center in (0; 4) and (0; -4)