== include(page="template/taskheader" task_id="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 la stânga dreaptei. 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, iar voi trebuie să le aflaţi poziţiile folosindu-vă de query-uri de tip:
* $? X{~1~} Y{~1~} X{~2~} Y{~2~}$, unde $X{~1~}$, $Y{~1~}$, respectiv $X{~2~}, Y{~2~}$ reprezintă coordonatele a două puncte în plan. Veţi primi în schimb un număr care reprezintă numărul de puncte aflate la stânga dreptei determinată de punctele $(X{~1~}, Y{~1~}), (X{~2~}, Y{~2~})$ (vezi restricţii şi precizări pentru definiţia exactă).
* $! X{~1~} Y{~1~} X{~2~} Y{~2~} ... X{~N~} Y{~N~}$, unde $X{~P~}$, $Y{~P~}$, reprezintă coordonatele poziţiilor găsite. Punctele din acest query trebuie să fie sortate crescător după X, iar în caz de egalitate după Y, pentru a lua punctaj maxim. Acest tip de query se va face o singură dată.
N puncte ascunse. Se da N. La query se dau 2 puncte (X1, Y1) si (X2, Y2), iar programul afiseaza numarul de puncte (X3, Y3) pentru care determinantul ((X1, Y1, 1), (X2, Y2, 1), (X3, Y3, 1)) este strict pozitiv.
h2. Date de intrare
Se da N, numarul de puncte.
h2. Interacţiune
h2. Date de ieşire
Iniţial se citeşte din stdin numărul $N$. Trebuie să printaţi un query şi să daţi flush la stdout. Dacă faceţi un query de primul tip atunci trebuie să citiţi din stdin răspunsul la query, altfel închideţi programul.
2 tipuri de queryuri:
? X1 Y1 X2 Y2
! urmat de veectorul de puncte X1 Y1 X2 Y2 .... X2 YN
h2. Restricţii
* 1 ≤ N ≤ 2000
* Coordonatele punctelor sunt numere întregi.
* Pentru punctele ascunse, $1 ≤ X, Y ≤ 100.000$.
* Pentru interogari, $0 ≤ X, Y ≤ 10^9^$.
* Pentru $20$ puncte, $N ≤ 10$ şi pentru toate punctele $0 ≤ X, Y ≤ 10$.
* Pentru alte $20$ puncte, coordonatele $X{~i~}$ si $Y{~i~}$ a oricarui punct sunt distincte.
* Dacă folosiţi puncte cu coordonate neîntregi la query, luaţi $80%$ din punctajul pe test.
* Pentru toate subtaskurile mai puţin primul, dacă folosiţi între $75001$ şi $100000$ query-uri, luaţi $30%$ din punctajul pe test (această restricţie este multiplicativă cu cea precedentă).
* Pentru a obţine punctaj maxim pe test trebuie să folosiţi cel mult $75000$ query-uri.
* **Numărul maxim de query-uri permis este $100000$**
* **Dacă se dau două puncte identice la o interogare de tipul $1$, se vor lua 0 puncte, cu mesajul "Wrong interaction!"**
* **Dacă query-ul este invalid sau depăşiţi limita de query-uri veţi primi ca răspuns valoarea -1 şi se va termina programul.**
* Punctul $(X, Y)$ se află la stânga dreptei determinate de punctele $(A, B), (C, D)$ dacă şi numai dacă $AD + CY + XB > BC + DX + YA$
* Pentru punctele ascunse X, Y <= 1e5
* Pentru Query X, Y <= 1e9
h2. Exemplu
table(example). |_. stdin |_. stdout |_. Explicatie |
| 3
|
| Se citeşte numărul de puncte
|
|
| ? 1 5 4 2
| Query cu punctele (1, 5), (4, 2)
|
| 2
|
| Punctele (4, 5), (6, 2)
|
|
| ? 4 2 1 5
| Query cu punctele (4, 2), (1, 5)
|
| 1
|
| Punctul (1, 2)
|
|
| ! 1 2 4 5 6 2
| Punctele găsite
|
table(example). |_. hidden_points.in |_. hidden_points.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicaţie
!problema/hidden_points?HIDDEN.png 500x500!
...
== include(page="template/taskfooter" task_id="hidden_points") ==
