ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

## Discussion of Problem 1332. Genie Bomber

How to solve this problem?
Posted by HybridTheory 28 Oct 2004 17:02
I've no idea.Could anybody help me?
Re: How to solve this problem?
Posted by Roman Lipovsky 28 Oct 2004 17:34
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: (+)
Posted by Victor Barinov (TNU) 28 Oct 2004 20:30
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: (+)
Posted by HybridTheory 28 Oct 2004 20:48
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.
Posted by Victor Barinov (TNU) 28 Oct 2004 23:53
Re: Sorry, but I not understand what do you mean.
Posted by HybridTheory 29 Oct 2004 06:19
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. (-)
Posted by Victor Barinov (TNU) 29 Oct 2004 12:57
Re: Sorry, but I not understand what do you mean.
Posted by Roman Lipovsky 29 Oct 2004 16:27
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
No subject
Posted by HybridTheory 30 Oct 2004 16:43
Thanks.
Re: How to solve this problem? Here is my solution: (+)
Posted by Oberon (Yura Znovyak) 1 Feb 2005 02:32
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? (-)
Posted by Victor Barinov (TNU) 1 Feb 2005 19:55
I do not claim that it is 4...
Posted by Oberon (Yura Znovyak) 1 Feb 2005 23:44
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...
Posted by Victor Barinov (TNU) 2 Feb 2005 00:19
Ok. my e-mail is  marilyn_manson@bk.ru
Re: I do not claim that it is 4...
Posted by Nguyễn Đình Tư (DHSP) 10 Jul 2005 23:53
I think Vic right

sorry my bad English
How to build circle by a single pair of points? (+)
Posted by xakac [BMSTU] 4 Aug 2006 23:51
Victor Barinov (TNU) wrote 28 October 2004 20:30
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? (+)
Posted by Victor Barinov (TNU) 5 Aug 2006 04:19
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? (+)
Posted by nistaman 31 Dec 2006 03:42
Why 2 circles?
And what is the center of those circles?
Re: How to build circle by a single pair of points? (+)
Posted by format_jam 3 Apr 2009 08:21
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? (+)
Posted by PrankMaN 24 Aug 2013 17:48
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)