1503. Вписанные треугольники

На границе окружности с центром в начале координат и радиусом r заданы n различных точек. Поскольку все точки расположены на одной окружности, то любые три из них не коллинеарны, и поэтому образуют треугольник. Вам необходимо вычислить суммарную площадь всех этих треугольников.

Вход. Состоит из не более чем 16 тестов. Каждый тест начинается двумя целыми числами n (0 £ n £ 500) и r (0 < r £ 100). Через n обозначено количество точек, а через r радиус окружности. Центр окружности находится в центре координат. Далее следуют n строк, каждая из которых содержит действительное число θ (0.0 ≤ θ < 360.00), которое определяет угол в градусах между точкой и направлением x-оси. Например, если θ равно 30.00 градусов, то соответствующая точка имеет декартовы координаты (r×cos(30.00°), r×sin(30.00°)). Последняя строка содержит n = r = 0 и не обрабатывается.

Выход. Для каждого теста в отдельной строке вывести целое число – суммарную площадь (округленную до ближайшего целого) всех возможных треугольников, образованных заданными n точками.

Пример входа	Пример выхода
5 10 10.00 100.00 300.00 310.00 320.00 3 20 10.00 100.00 300.00 0 0	286 320

РЕШЕНИЕ

геометрия + перебор

Анализ алгоритма

Рассмотрим треугольник ABC. Вычислим его площадь как площадь круга минус площадь трех черных сегментов, как показано на рисунке.

Таким образом, искомая площадь равна минус суммарная площадь сегментов, которую как далее будет показано, можно вычислить за время O(n²).

Напомним, что площадь сектора радиуса r, стягиваемого углом a, равна . Площадь соответствующего сегмента равна площади сектора минус площадь равнобедренного треугольника с боковой стороной r и углом при вершине a. Таким образом, площадь сегмента равна

S_{сегмента} = =

Изначально положим искомую площадь всех треугольников равной res = = . После чего из res будем последовательно вычитать площади сегментов.

Рассмотрим отрезок, соединяющий точки P_i и P_j (i < j). В переменной s вычислим площадь сегмента, который мы проходим при движении по окружности от точки P_i к P_j против часовой стрелки (по направлению возрастания углов).

Сегмент площади s вычитается из общей площади res столько раз, сколько точек находится между P_i и P_j со стороны сегмента площади r² – s. Сегмент площади s вычитается при подсчете площадей треугольников P_iP_jP_k, где k пробегает по точкам, расположенным от P_j до P_i при движении против часовой стрелки (k принимает значения j + 1, j + 2, …, i – 2, i – 1). Таких точек будет pnts1 = n – (j – i + 1). Вычитаем из res pnts1 раз площадь s.

Соответственно точек со стороны сегмента площади s будет pnts2 = n – pnts1 – 2. Именно столько раз необходимо вычитать площадь сегмента r² – s из res.

Реализация алгоритма

Считаем градусную меру точек, переведем ее в радианную и занесем в ячейки массива d (d[i] содержит радианную меру i - ой точки).

double d[MAX];

Пока не достигнем конца файла, читаем входные данные.

while(scanf("%d %d",&n,&r), n + r)

{

Заносим радианную меру точек в массив d.

for(i = 0; i < n; i++)

{

scanf("%lf",&d[i]);

d[i] = d[i] * PI / 180;

}

Сортируем массив d по возрастанию.

sort(d,d + n);

В переменную res изначально заносим площадь, равную площади кругов радиуса r, то есть значение = . Переменной r2 присвоим значение , а sq площадь одного круга, то есть .

res = n * (n - 1) * (n - 2) / 6 * PI * r * r;

r2 = r * r / 2.0; sq = PI * r * r;

При помощи индексов i и j совершаем перебор пар точек.

for(i = 0; i < n; i++)

for(j = i + 1; j < n; j++)

{

Вычисляем угол alfa между точками i и j, который равен d[j] – d[i]. Если alfa меньше , то при движении от i к j мы проходим по меньшему сегменту и его площадь равна . Иначе при движении от i к j мы проходим по большему сегменту и в таком случае его площадь равна , где положено .

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

alfa = d[j] - d[i];

if (alfa < PI)

s = r2 * (alfa - sin(alfa));

else

{

alfa = 2 * PI - alfa,

s = sq - r2 * (alfa - sin(alfa));

}

Количество точек points, лежащих на сегменте, площадь которого , равно n – (j – i + 1). Таким образом из значения res необходимо вычесть points раз площадь сегмента s.

points = n - (j - i + 1);

res -= s * points;

Количество точек, лежащих на сегменте площади s, равно points = n – points – 2. Площадь противоположного сегмента равна sq – s. Остается вычесть ее из res points раз.

points = n - points - 2;

res -= (sq - s) * points;

}

Выводим на печать искомую площадь res.

printf("%.0lf\n",res);

}