Rakiety
Limit pamięci: 32 MB
Na płaskiej mapie wyznaczono dwa rozłączne, -elementowe zbiory punktów: i . Żadne trzy punkty ze zbioru nie są współliniowe. W punktach ze zbioru rozlokowane są rakiety typu ziemia-ziemia, natomiast w punktach ze zbioru znajdują się obiekty wroga, które trzeba zniszczyć. Rakiety mogą lecieć jedynie w linii prostej, a tory rakiet nie mogą się przecinać. Chcemy dla każdej rakiety wyznaczyć cel, który powinna zniszczyć.
Zadanie
Napisz program, który:
- wczytuje ze standardowego wejścia współrzędne punktów ze zbiorów i ,
- wyznacza zbiór parami nie przecinających się odcinków i takich, że jeden koniec każdego odcinka należy do zbioru , podczas gdy drugi należy do zbioru ,
- wypisuje wynik na standardowe wyjście.
Wejście
W pierwszym wierszu standardowego wejścia jest zapisana jedna liczba naturalna , , równa liczności zbiorów i .
W każdym z kolejnych wierszy wejścia jest zapisana para liczb całkowitych z przedziału oddzielonych pojedynczym odstępem. Są to współrzędne punktu na płaszczyźnie (najpierw współrzędna , potem współrzędna ). Pierwsze z tych wierszy zawiera współrzędne punktów ze zbioru , natomiast ostatnie wierszy zawiera współrzędne punktów ze zbioru . W wierszu o numerze znajdują się współrzędne punktu , natomiast w wierszu o numerze znajdują się współrzędne punktu , .
Wyjście
Standardowe wyjście powinno składać się z wierszy. W -tym wierszu należy zapisać jedną liczbę naturalną taką, że odcinek należy do wyznaczonego zbioru odcinków (innymi słowy, że rakieta z punktu ma zniszczyć obiekt położony w punkcie ).
Przykład
Dla danych wejściowych:
4
0 0
1 5
4 2
2 6
1 2
5 4
4 5
3 1
poprawną odpowiedzią jest:
2
1
4
3
Autor zadania: Wojciech Rytter.