Latarnia
Limit pamięci: 256 MB
W środku nocy Bitocy włączył latarnię przy wejściu do budynku, w którym mieszka Bajtazar.
Światło latarni nie daje spać Bajtazarowi.
Co prawda, latarnia nie świeci bezpośrednio w okno Bajtazara, ale jej światło odbija się od innych
okien i wpada w okno Bajtazara.
Bajtazar nie może zasnąć i denerwuje się.
Żeby czymś zająć umysł, zamiast się denerwować, Bajtazar wygląda przez okno i zastanawia się,
w które jeszcze okna świeci latarnia.
Problem ten wciągnął go na tyle, że zapomniał o śnie i zadzwonił do Ciebie, prosząc o pomoc.
Znasz Bajtazara nie od dziś i wiesz, że póki nie napiszesz dla niego programu rozwiązującego ten problem,
sam(a) też nie pójdziesz spać.
Bajtazar mieszka w budynku , w którym jest okien.
Latarnia znajduje się na samym dole budynku, na ścianie.
Naprzeciwko budynku stoi budynek , oddalony o 10 metrów.
Jego ściana jest równoległa do ściany budynku Bajtazara.
Budynek ma okien.
Światło latarni rozchodzi się po liniach prostych, chyba że trafi w okno -
wtedy mówimy, że latarnia świeci w to okno, a światło latarni odbija się od niego
(zgodnie z zasadą "kąt padania równa się kątowi odbicia").
Na ścianach budynków mamy określone układy współrzędnych - oś jest pozioma,
oś jest pionowa, osie na obu ścianach mają zgodne zwroty,
a punkty na obu ścianach leżą dokładnie naprzeciwko siebie.
Okna to prostokąty położone na ścianach o bokach równoległych do osi układu współrzędnych.
Światło nie odbija się od brzegów okien.
Ponadto wiadomo, że okna w obrębie jednego budynku mają parami rozłączne wnętrza.
Latarnia znajduje się na ścianie budynku w punkcie i nie znajduje się we wnętrzu
ani na brzegu żadnego z okien.
Wejście
W pierwszym wierszu standardowego wejścia znajdują się dwie liczby całkowite oraz (),
oddzielone pojedynczym odstępem, oznaczające liczbę okien w pierwszym i w drugim budynku.
W kolejnych wierszach opisane są okna w budynku Bajtazara (budynek ), po jednym w wierszu.
W -szym wierszu (dla ) znajdują się cztery liczby całkowite , , ,
(,
), pooddzielane pojedynczymi odstępami.
Taka czwórka oznacza, że -te okno znajdujące się w budynku stanowi prostokąt na ścianie budynku,
którego lewy dolny i prawy górny róg mają współrzędne i , wyrażone w metrach.
Następnie w kolejnych wierszach, w tym samym formacie, opisane są okna budynku .
Wyjście
Twój program powinien wypisać w pierwszym wierszu standardowego wyjścia liczbę okien budynku ,
w które świeci latarnia.
Możesz założyć, że dla każdych danych wejściowych będzie istniało co najmniej jedno takie okno.
W drugim wierszu należy wypisać numery tych okien, podane w kolejności rosnącej,
pooddzielane pojedynczymi odstępami (okna numerujemy od ).
Przykład
Dla danych wejściowych:
3 3
-1 2 1 4
-1 5 1 7
-3 8 -2 20
-1 1 1 2
-1 4 1 5
-1 7 1 10
poprawną odpowiedzią jest:
2
1 2
Wyjaśnienie do przykładu:
Do pierwszego okna budynku światło dolatuje, odbiwszy się od pierwszego okna w budynku
(np. odbija się w punkcie budynku i trafia w punkt budynku ).
Żeby trafić w drugie okno budynku , światło latarni musi odbić się trzy razy -
ten sam promień trafia w punkt w drugim oknie budynku , a potem w w drugim oknie budynku .
Światło nie trafia w trzecie okno budynku , tylko obok niego.
Należy dodać, że światło latarni oświetla cały budynek , na rysunku natomiast
zaznaczono tylko te promienie świetlne, które po odbiciu oświetlają okna budynku .
Autor zadania: Jakub Onufry Wojtaszczyk.