In the event of technical difficulties with Szkopuł, please contact us via email at [email protected].
If you would like to talk about tasks, solutions or technical problems, please visit our Discord servers. They are moderated by the community, but members of the support team are also active there.
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.
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 .
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 ).
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.