Обсуждение @ 1332. Джинн-бомбардировки @ Timus Online Judge

Показать все сообщения Спрятать все сообщения

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)

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