z-ray
Mali Z igra novu igru. Igra se sastoji od 2D koordinatnog sustava u kojemu je zadano N duzina i jedna tocka (x,y). Mali Z treba povuci polupravac iz tocke (x,y).
Broj bodova jednak je broju presjecenih duzina. Malog Z-a zanima koji je najmanji a koji najveci moguci broj bodova koji moze osvojiti te vas trazi za pomoc.
InputU prvom redu standardnog ulaza nalaze se 3 razmakom odvojena cijela broja N ( 1 <= N <= 200000 ), x, y ( 0 <= |x|, |y| < 10000 ).
U sljedecih N linija nalazi se po 4 razmakom odvojena cijela broja x1i, y1i, x2i, y2i( 0 < |x1i|, |y1i|, |x2i|, |y2i| <= 10000 ) koji predstavljaju koordinate krajnjih tocaka duzine.
Napomena:
- sve tocke u ulazu ce biti razlicite
- tocke ( x1i, y1i ), ( x2i, y2i ) i ( x, y ) nece biti kolinearne.
- Mali Z za liniju dobiva 1 bod ako ju presjece u bilo kojem njenom djelu, ukljucujuci i rubne tocke.
U sljedecih N linija nalazi se po 4 razmakom odvojena cijela broja x1i, y1i, x2i, y2i( 0 < |x1i|, |y1i|, |x2i|, |y2i| <= 10000 ) koji predstavljaju koordinate krajnjih tocaka duzine.
Napomena:
- sve tocke u ulazu ce biti razlicite
- tocke ( x1i, y1i ), ( x2i, y2i ) i ( x, y ) nece biti kolinearne.
- Mali Z za liniju dobiva 1 bod ako ju presjece u bilo kojem njenom djelu, ukljucujuci i rubne tocke.
OutputU prvom i jedinom redu standardnog izlaza treba ispisati 2 razmakom odvojena cijela broja, najmanji i najveci moguci broj bodova koji Mali Z moze osvojiti.
Ulaz:
Izlaz:
4 1 2
3 -1 -2 8
4 0 -2 -2
-2 -3 -3 4
-4 3 2 4Izlaz:
1 2Ulaz:
Izlaz:
2 -1 5
1 3 3 2
-4 2 2 -5Izlaz:
0 1Ulaz:
Izlaz:
3 0 0
1 3 3 1
2 3 1 -1
-4 2 2 -5Izlaz:
0 2Image: example
Slika odgovara 3. primjeru. Duzine su oznacene plavom bojom. Crvenom bojom oznacen je jedan od polupravaca koji osvaja najmanje bodova, zelenom bojom oznacen je jedan od polupravaca koji osvaja najvise bodova.
Submit solution
Coming laterThe grading service will be connected in a later migration step. You can inspect the task and your previous results now.