Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | hidden_points.in, hidden_points.out | Sursă | Winter Challenge 2020 |
| Autor | Alexandru Petrescu, Mihai-Cristian Popescu | Adăugată de |  Comisia •winterchallenge2020 |
| Timp execuţie pe test | 2.1 sec | Limită de memorie | 200000 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Hidden Points
Jon şi Daenerys trebuie să găsească un plan de atac pentru a învinge armata morţilor. Cei doi ştiu exact numărul inamicilor, dar nu şi poziţiile acestora. Pentru a afla locaţiile lor, Jon îi dă lui Daenerys ecuaţia unei drepte iar apoi ea zboară cu dragonii săi şi numără câţi inamici se află strict sub dreaptă. Cei doi repetă procesul până când Jon reuşeşte să găsească poziţiile tuturor inamicilor. Deoarece Jon nu se pricepe la probleme de geometrie, acesta vă roagă pe voi să îl ajutaţi. Vi se dă N, numărul inamicilor, şi limitele coordonatelor în plan ale acestora, iar voi trebuie să le aflaţi poziţiile folosindu-vă de query-uri de tip:
"? X1 Y1 X2 Y2", unde X1, Y1, respectiv X2, Y2 reprezintă coordonatele a două puncte în plan. Veţi primi în schimb un număr care reprezintă numărul de puncte aflate sub dreaptă.
"! X1 Y1 X2 Y2 ... XN YN", unde XP, YP, reprezintă poziţiile găsite. Acest tip de query se va face o singură dată.
Date de intrare
Se dă N, numărul de inamicilor şi lim, limita superioară pentru coordonatele punctelor în modul.
Date de ieşire
2 tipuri de queryuri:
? X1 Y1 X2 Y2
! urmat de vectorul de puncte X1 Y1 X2 Y2 .... XN YN
Restricţii
- Pentru punctele ascunse 0 < X, Y <= 1e5
- Pentru Query 0 <= X, Y <= 1e5 + 1
pentru teste in valoare de A puncte, N <= 2.000 si sunt necoliniarepentru teste in valoare de B puncte, N <= 2.000pentru teste in valoare de C puncte, N <= 50.000 si sunt necoliniarepentru teste in valoare de D puncte, N <= 50.000A + B e vreo 75A + C e vreo 80-85A + B + C + D = 100- daca folositi double la query, luati 80% din punctajul pe test
- daca folositi peste 5Nlog queryuri, luati 30% (?) din punctajul pe test
Exemplu
| stdin | stdout |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicaţie
...
