ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1332. Джинн-бомбардировки

How to solve this problem?
Послано HybridTheory 28 окт 2004 17:02
I've no idea.Could anybody help me?
Re: How to solve this problem?
Послано Roman Lipovsky 28 окт 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: (+)
Послано Victor Barinov (TNU) 28 окт 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: (+)
Послано HybridTheory 28 окт 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.
Послано Victor Barinov (TNU) 28 окт 2004 23:53
Re: Sorry, but I not understand what do you mean.
Послано HybridTheory 29 окт 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. (-)
Послано Victor Barinov (TNU) 29 окт 2004 12:57
Re: Sorry, but I not understand what do you mean.
Послано Roman Lipovsky 29 окт 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
Послано HybridTheory 30 окт 2004 16:43
Thanks.
Re: How to solve this problem? Here is my solution: (+)
Послано Oberon (Yura Znovyak) 1 фев 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? (-)
Послано Victor Barinov (TNU) 1 фев 2005 19:55
I do not claim that it is 4...
Послано Oberon (Yura Znovyak) 1 фев 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...
Послано Victor Barinov (TNU) 2 фев 2005 00:19
Ok. my e-mail is  marilyn_manson@bk.ru
Re: I do not claim that it is 4...
Послано Nguyễn Đình Tư (DHSP) 10 июл 2005 23:53
I think Vic right

sorry my bad English
How to build circle by a single pair of points? (+)
Послано xakac [BMSTU] 4 авг 2006 23:51
Victor Barinov (TNU) писал(a) 28 октября 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? (+)
Послано Victor Barinov (TNU) 5 авг 2006 04:19
Of course not! Both points are lying on the circle
Re: How to build circle by a single pair of points? (+)
Послано PSV 21 дек 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? (+)
Послано nistaman 31 дек 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? (+)
Послано format_jam 3 апр 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? (+)
Послано PrankMaN 24 авг 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)