Сперва надо отсортировать все окружности по углу(угловая сортировка). Можно было сортировать по

тангенсу угла. Дальше надо было придумать формулу для нахождения длины части веревки соединяющей

две последовательные окружности. Точную формулу можете вывести сами, для этого нужно знать, как

вычислять расстояние между двумя точками в декартовой системе координат, и знать теорему

косинусов.

Сложность будет $O(NlogN)$.

Бізге ең ұзын ұзындықты табу керек.Ол үшін:

1.Ең қысқа қабырғаны табу керек

2.Геронның формуласын қолданып,ауданын табу керек.

А=$\sqrt{s(s-a)(s-b)(s-c)}$, $s = \frac{a+b+c}{2}$;

 толық мәлімет  http://en.wikipedia.org/wiki/Heron's_formula

3.Келесі формула: Аудан тең ұзындық көбейтілген  ұзындық түскен қабырға.Екеуін теңестіріп ұзындықты табамыз.

А.Қ.Ж.Ал,іске сәт!!!!!!!!

А.Қ.Ж.(аяғына қосқан жазу)

Любые две стороны должны быть длиннее третьей, чтобы получился треугольник.

a+b>c and a+c>b and b+c>a

Разница двух сторон всегда короче третьей.

And |a-b|<c and |a-c|<b and |b-c|<a

a:=y2-y1; b:=x1-x2; c:=-x1(y2-y1)+y1(x2-x1); t:=sqrt(aa+bb); d:=abs((ax3+b*y3+c)/t);

Во-первых, будем считать, что A1 < B1 и A2 < B2 (если это не так, то добьемся этого поменяв числа в соответствующей паре местами). Далее, нарисовав один-два случая можно заметить, что хорды будут пересекаться или касаться только в трех случаях: * они совпадают, то есть обе вершины общие: ((A1 == A2) && (B1 == B2)) * одна вершина общая: ((A1 == A2) || (A1 == B2) || (A2 == B1) || (A2 == B2)) * вершины разные, и для каждой хорды выполняется следующее условие: если окружность разрезать по этой хорде, то вершины другой хорды должны быть в разных частях окружности: ((A1 < A2) && (A2 < B1) != (A1 < B2) && (B2 < B1)) Все решение заключается в проверке этих трех условий

.

.

Нахождение площади простого многоугольника Пусть дан простой многоугольник (т.е. без самопересечений, но не обязательно выпуклый), заданный координатами своих вершин в порядке обхода по или против часовой стрелки.

Это легко сделать, если перебрать все рёбра и сложить площади трапеций, ограниченных каждым ребром. Площадь нужно брать с тем знаком, с каким она получится (именно благодаря знаку вся "лишняя" площадь сократится). Т.е. формула такова:

S += (X2 - X1) * (Y1 + Y2) / 2

Две окружности могут быть идентичными, или пересекатся в двух точках, в одной точке или не пересекатся.

Возьмем l как дистанция между двумя центрами ($\sqrt{(x-x1)^2 + (y-y1)^2}$).

Если l = r+r1 или l = |r-r1| они пересекаются в одной точке, если же |r-r1| < l и l < r+r1 они пересекаются в двух точках, если центры и радиусы одинаковы они одинаковые и ответом будет бесконечно точек.

И так, переходим к нахождению точек. По теореме косинусов найдем длину |OH|.

$r^2 + l^2 - 2lr \times cos(alfa) = \frac{r^2 + l^2 - r1^2}{2*l}$

И по теореме Пифагора $|HP| = \sqrt{r^2 - |OH|^2}$;

Теперь находим вектор v|OH| = |OH| / l * v|O1O2|. v|O1O2| = вектор между двумя центрами (x1-x, y1-y).

Теперь находим перпендикуляр к вектору O1O2. V(y1-y, x1-x). Потом Находим вектор |HP| = |HP|/|V| * V. |V| = длина вектора V.

Ответами будет:

1. O.x + OH.x - HP.x

2. O.y + OH.y - HP.y

3. O.x + OH.x + HP.x

4. O.y + OH.y + HP.y

Hint :

Единственно, что нужно учесть это то, что точка может быть проекцированна на отрезке. А потом можно приступать к решению))) И еще используйте long, а то на 7 тесте вылетит)))

Ну, задача не сложная, нужно проверить лежит ли точка в выпуклом многоугольнике. Строить оболочку не надо, она и так построена, осталось лишь суметь за "быстро" проверять. Можно сделать бинарный поиск. Будем брать l, r и сравнивать векторным произведением вектор из первой точки в (l + r)/2 с вектором из первой точки в точку запроса, если оборот по часовой стрелке, сдвигаем r в (l + r)/2 иначе наоборот. В конечном счете у нас будут два соседних вектора(точки) l и r. Осталось проверить лежит ли сторого точка запроса в треугольнике lrb, где b это первая точка.

Задачка на геометрию. Всё что требуется решить систему уравнений с двумя не известными.

$a_1 \times x + b_1 \times y + c_1 = 0$
$a_2 \times x + b_2 \times y + c_2 = 0$

можно решать обычным способом

$a_2 \times (a_1 \times x + b_1 \times y + c_1 = 0)$
$\underline{-a_1 \times (a_2 \times x + b_2 \times y + c_2 = 0)}$
$a_2\times b_1\times y - a_1\times b_2\times y + a_2\times c_1 - a_1 \times c_2 = 0$
выносим _y_ за скобки
$y \times (a_2\times b_1 - a_1\times b_2) + a_2\times c_1 - a_1 \times c_2 = 0$
перекидываем все на другую сторону и получаем
$y = \frac{a_1 \times c_2 - a_2\times c_1}{a_2\times b_1 - a_1\times b_2}$

а вот тут дальше я раньше делал ошибку. я просто подставлял наш найденный y в одно из уравнений линии и находил x.
$x = \frac{b_1 \times y + c_1}{-a1}$
но если линия горизонтальна то a₁ будет равно нулю, и за токое получаем Runtime-Error. Кстати выражение $a_2\times b_1 - a_1\times b_2$ будет равно нулю только при случае когда линии паралельны.

что делать?
для того чтобы не иметь дела с такой проблемой как DevisionByZero, надо так же решить систему уравнений и для x( то есть теперь исключить y и найти x).

В этой задаче нам дано три окружности.И наша основная задача состоит в нахождении пересечения этих 3ех окружностей.В кратце это и должно быть решением.

Если вы умеете находить точку пересечения двух окружностей ,нахождение пересечения трех окружностей не составит вам труда.Это делается так:просто находим точки пересечения двух ,и проверяем с третьей =)

Если же вы не знаете как это сделать советую научится)))

Прочитайте в Кормене))может там и найдете ))