Submit solution

Points: 1
Time limit: 2.0s
Memory limit: 64M

Author:
Problem type

Đurica putuje vozom kroz Vojvodinu i uživa razgledajući predivne poljane. Tokom putovanja on često (i ovaj put) fiksira položaj glave i razgleda, ne bi li bio siguran da neće propustiti ni jedan metar prelepog prizora, kao i da će svakom pokloniti isto vremena. Iz tih razloga, položaj njegove glave ostaje fiksiran tokom putovanja. Poljane su oblika pravougaonika, sa stranicama paralelnim ili normalnim na prugu.

Radi lakšeg opisa, pretpostavićemo da se pruga nalazi na x-osi, a poljane u prvom kvadrantu koordinatnog sistema. Svaka poljana je predstavljena svojim donjim-levim i gornjim-desnim temenom. Đuricin pogled ćemo predstaviti polupravom koja menja svoju početnu tačku duž x-ose u pozitivnom smeru. Nagib poluprave na x-osu je izražen u stepenima, a ima vrednost alfa.

Nakon svog putovanja, Đurica se zamislio i zapitao koji je najveći broj poljana koje je on u nekom momentu posmatrao, tj. presekao pogledom. Pošto ćete vi dobiti opis poljana i ugao nagiba alfa, pomozite Đurici i izračunajte koji je najveći broj poljana u nekom momentu koje je Đurica presekao pogledom.

Ulaz:

(Ulazni podaci se učitavaju sa standardnog ulaza) U prvom redu nalaze se prirodni brojevi n (1 ≤ n ≤ 100.000) i alfa (1 ≤ alfa ≤ 90), koji predstav aju broj po ana i ugao nagiba Đuricinog pogleda u stepenima, redom. U narednih n redova su data po četiri prirodna broja x1, y1, x2, y2 (1 ≤ x1 < x2 ≤ 100.000, 1 ≤ y1 < y2 ≤ 100.000) koji označavaju donje-levo i gornje-desno teme poljana, redom - u i-tom redu koordinate za i-tu poljanu.

Izlaz:

(Izlazni podaci se ispisuju na standardni izlaz) U prvom i jedinom redu ispisati jedan ceo broj koji predstavlja najveći broj poljana koje je Đurica u nekom momentu video.

Primer:

standardni ulaz      standardni izlaz
4 45
3 1 5 2
7 2 8 3
7 4 9 5
2 3 5 5
        
3

Objašnjenje.

Kada se Đurica bude nalazio na koordinati 4 x-ose, videće prve tri poljane date na ulazu. Poljani pripada i rub pravougaonika koji je ograničava. Dovoljno je posmatrati samo jednu tačku, na primer teme, poljane da se smatralo da pogled preseca poljanu.


Comments

There are no comments at the moment.