How to solve this problem?

I've no idea.Could anybody help me?

Re: How to solve this problem?

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.

Re: How to solve this problem? Here is my solution: (+)

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 :-)

Re: How to solve this problem? Here is my solution: (+)

Thank you first.

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

*Edited by author 28.10.2004 20:50*

Sorry, but I not understand what do you mean.

Re: Sorry, but I not understand what do you mean.

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.

Sorry, It is hard to me explain it in English. But if You consist some variants, You'll understand it. (-)

Re: Sorry, but I not understand what do you mean.

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*

Re: How to solve this problem? Here is my solution: (+)

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.

Why you think, that my solution would be 4? (-)

I do not claim that it is 4...

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?

Re: I do not claim that it is 4...

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

Re: I do not claim that it is 4...

I think Vic right

sorry my bad English

How to build circle by a single pair of points? (+)

Build 2 circles thru all pairs of points (it is n*(n-1) circles)

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*Re: How to build circle by a single pair of points? (+)

Of course not! Both points are lying on the circle

Re: How to build circle by a single pair of points? (+)

Posted by

PSV 21 Dec 2006 22:13

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

Re: How to build circle by a single pair of points? (+)

Why 2 circles?

And what is the center of those circles?

Re: How to build circle by a single pair of points? (+)

2 points can make 2 circles with the exact R.

(from two different directions!)

I am also confused just know. :)

Re: How to build circle by a single pair of points? (+)

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)