Problem description

Back
Show PDF
Trójkąty równoramienne
(I)
Limit pamięci: 64 MB
Limit czasu: 5.00 s

Na płaszczyźnie znajduje się N parami różnych punktów. Twoim zadaniem jest napisać program, który wczyta ich współrzędne, a następnie wyznaczy i wypisze liczbę różnych, trzyelementowych podzbiorów1 zbioru wszystkich N punktów, będących zbiorami wierzchołków jakiegoś niezdegenerowanego2 trójkąta równoramiennego.

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba całkowita N, oznaczająca liczbę wszystkich punktów.
W i-tym z kolejnych N wierszy znajdują się dwie liczby całkowite xi, yi, oddzielone pojedynczym odstępem, oznaczające współrzędne i-tego punktu.

Wyjście

W pierwszym (i jedynym) wierszu wyjścia powinna się znaleźć jedna liczba całkowita będąca odpowiedzią do zadania.

Ograniczenia

1 ≤ N ≤ 3000
 − 109 ≤ xi yi ≤ 109

Przykład

Wejście Wyjście Wyjaśnienie 
5
0 0
-1 -1
-1 1
1 -1
1 1

8

W wersji HTML poniżej znajduje się rysunek
Szukane podzbiory to {1, 2, 3}, {1, 3, 5}, {1, 4, 5}, {1, 2, 4}, {2, 3, 5}, {2, 3, 4}, {2, 4, 5}, {3, 4, 5}.

  1. Czyli trójki bez porządku. Przykładowo: {1, 2, 3} i {2, 3, 1} to ten sam zbiór i powinien być policzony co najwyżej raz.↩︎

  2. Zbiór wierzchołków niezdegenerowanego trójkąta definiujemy jako zbiór trzech niewspółliniowych punktów. Dodatkowo, trójkąt (zbiór punktów) ten jest równoramienny, gdy w trójkącie (figurze geometrycznej), powstałym przez dorysownie odcinków między punktami, istnieją co najmniej dwa ramiona, które są równe.↩︎