In the event of technical difficulties with Szkopuł, please contact us via email at szkopul@fri.edu.pl.
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.