Trylobit bardzo lubi budować metro. Zaprojektował $n$ linii, z których każda ma $n+1$ potencjalnych lokalizacji stacji, określonych za pomocą współrzędnych na płaszczyźnie.
Aby urozmaicić korzystanie z metra, Trylobit postanowił, że każda linia będzie odcinkiem! Oznacza to, że dla każdej linii Trylobit wybierze tylko dwa punkty i połączy je odcinkiem. Aby zmaksymalizować trudności przesiadkowe pasażerów, Trylobit wymaga, aby liczba punktów przecięcia między każdą parą z $n$ zbudowanych linii metra była jak najmniejsza. Uwaga: punkty przecięcia obejmują również stacje początkowe i końcowe. Zaplanuj poprawne rozwiązanie.
W uproszczeniu: Dany jest zbiór punktów w płaszczyźnie dwuwymiarowej, składający się z $n$ kolorów, gdzie każdy kolor ma $n+1$ punktów. Należy wybrać dwa różne punkty dla każdego koloru i połączyć je odcinkiem tak, aby łączna liczba punktów przecięcia wszystkich $n$ odcinków była minimalna. Wypisz konstrukcję rozwiązania.
Uwaga: Jeśli dwa odcinki są współliniowe, liczba punktów przecięcia jest definiowana jako nieskończoność. Wszystkie nieskończoności uznaje się za równe.
Zadanie zawiera wiele zestawów danych. Pierwsza linia zawiera liczbę całkowitą $T$ oznaczającą liczbę zestawów danych. Dla każdego zestawu danych:
Pierwsza linia zawiera liczbę całkowitą $n$ oznaczającą liczbę linii.
Następnie $n$ linii, z których każda zawiera $2n+2$ liczby całkowite. Dla każdej linii $i$, pary liczb $(x_j, y_j)$ oznaczają współrzędne kolejnych stacji, przy czym stacje są numerowane od $1$ do $n+1$ w ramach danej linii.
Gwarantuje się, że wszystkie współrzędne stacji są parami różne.
Dla każdego zestawu danych wypisz $n$ linii, z których każda zawiera dwie liczby całkowite oznaczające numery stacji połączonych daną linią. Wystarczy podać dowolne poprawne rozwiązanie.
Przykład
Wejście 1
1 2 5 0 0 8 10 8 0 4 10 4 5 12
Wyjście 1
1 3 1 3
Uwagi
Na rysunku niebieskie i czerwone punkty reprezentują stacje odpowiednio pierwszej i drugiej linii, a niebieska i czerwona linia reprezentują wybrane połączenia.
Zauważ, że wystarczy podać dowolne poprawne rozwiązanie, więc:
1 2 2 3
również jest poprawną odpowiedzią.
| Podzadanie | Punkty | Dodatkowe ograniczenia |
|---|---|---|
| 1 | 30 | $n\le 5,\sum n\le 50$ |
| 2 | 20 | Istnieje permutacja tych $n(n+1)$ punktów taka, że współrzędne $i$-tego punktu to $(i,i)$ |
| 3 | 20 | $n\leq 100$ |
| 4 | 30 | Brak |
Dla wszystkich danych: $1\le n\le1000,\sum n\leq 2000$, $|x_i|,|y_i|\le10^9$.