Подразделы

Другие разделы

Дата и время

19/12/2024 19:44:14

Авторизация

4. Треугольники

Сложная задача, необходимо знание алгоритма быстрой сортировки.

Сначала докажем, что треугольник с целочисленными координатами вершин равносторонним быть не может. Площадь равностороннего треугольника равна `{a^2\ sqrt(3)}/4`, где `a` – длина стороны. Для вершин с целыми координатами `a^2` будет целым, следовательно площадь равностороннего будет выражаться иррациональным числом. Площадь многоугольника с целочисленными координатами вершин может быть вычислена по формуле Пика как `p\ +\ q/2\ -\ 1`, где `p` – количество точек с целочисленными координатами внутри многоугольника, а `q` – на границе многоугольника, включая вершины. Площадь треугольника с целочисленными координатами вершин будет рациональным числом. Получили противоречие, следовательно, можно при решении задачи не рассматривать равносторонние треугольники.

Возьмем какую-нибудь точку из заданного множества и отсортируем остальные вершины по квадрату расстояния до нее. Для сортировки необходимо использовать быструю сортировку со временем работы `O(N\ log\ N)`. Если существует `k` точек, лежащих на одинаковом расстоянии от выбранной точки, то из них можно составить `{k*(k-1)}/2` равнобедренных треугольников. Из этого количества нужно вычесть вырожденные треугольники, образованные центрально-симметричными точками относительно выбранной. Для этого либо сравниваем попарно положения точек, лежащих на одинаковом расстоянии от выбранной (сложность такого сравнения `O(N^2)`, но из-за геометрической основы задачи общее количество таких сравнений будет небольшим и общее время работы алгоритма не ухудшится), либо отсортировать после ввода все точки по `x`, затем по `y` и выполнять поиск центрально-симметричной точки относительно выбранной точки для всех остальных точек за время `O(log\ N)`.

Такие действия необходимо выполнить для всех точек, время работы алгоритма с использованием двух сортировок равно `O(N^2\ log\ N)`. Основная часть решения выглядит так:

var N,i,j,k,m,jj:longint;
  x,y:array[1..1500] of longint;
  d:array[1..1500] of record d:int64;x,y:longint; end;;
  res:int64;
...
  { ввод данных }
  readln(N);
  for i:=1 to N do
    readln(x[i],y[i]);
  res:=0;
  for i:=1 to N do
  begin
    { заполняем массив с расстояниями и относительными координатами }
    k:=0;
    for j:=1 to N do
      if i<>j then
      begin
        inc(k);
        d[k].d:=sqr(int64(x[i]-x[j]))+sqr(int64(y[i]-y[j]));
        d[k].x:=x[j]-x[i];
        d[k].y:=y[j]-y[i];
      end;
    { сортировка }
    qsort(1,k);
    j:=1;
    while j<=k do
    begin
      { считаем количество точек на одинаковом расстоянии }
      m:=1;
      while (j+m<=k) and (d[j].d=d[j+m].d) do
      begin
        { вычитаем вырожденные треугольники }
        for jj:=j to j+m-1 do
          if (d[j+m].x=-d[jj].x) and (d[j+m].y=-d[jj].y) then
            dec(res);
        inc(m);
      end;
      res:=res+m*(m-1) div 2;
      j:=j+m;
    end;
  end;
  writeln(res);

Назад

Подразделы

Другие разделы

Дата и время

Авторизация

4. Треугольники