Qalaktik Müharibə Ağaları
Düzgün versiya
Nəhayət, qalaktika sülhə qovuşacaqmı? Bütün müharibə ağaları məkanı öz aralarında bölüşdürmək üçün bir araya gəliblər. Danışıqlar xeyli irəliləyib və müharibə ağaları kimin nə alacağına dinc yolla razılaşıblar. İlk olaraq, 2 ölçülü qalaktik xəritə sonsuz xətlərin dəsti boyunca bölünərək sektorlara ayrılmalıdır. Ən böyük döyüş donanmasına malik müharibə ağası bir sektor seçəcək, sonra ikinci ən böyük donanmaya malik olan başqa bir sektor seçəcək və bu, hər kəs bir sektor alana qədər davam edəcək. Bu proses sektorlardan heç biri qalmayana qədər təkrarlanır.
Fərqli xətt dəstləri təklif olunub və bu alternativləri görüşə təqdim etmək sizin işinizdir. Sülhün təmin olunması üçün təklifləri bir qədər dəyişməyə hazırsınız. Müharibə ağaları ilə bağlı bir qədər təcrübəniz var və bilirsiniz ki, heç bir müharibə ağası başqasından az məkanla razılaşmayacaq, ona görə də sülhün olması üçün onların hamısı xəritədə tam eyni sahəni almalıdır. Məkan sonsuz olduğundan, xəritə də sonsuzdur. Buna görə də bəzi sektorlar sonsuz sahəyə malik olacaq, bu da hər kəsin istədiyi məkan miqdarıdır. Hər bir müharibə ağasının sonsuz sahəyə malik ən azı bir sektor ala bilməsi üçün neçə əlavə xətt əlavə etməlisiniz?
Giriş verilənləri
Girişin ilk sətiri iki müsbət tam ədədi W və N (1 ≤ W, N ≤ 100) ehtiva edir, bu da müharibə ağalarının sayını və məkanın təklif olunan bölgüsündəki xətlərin sayını göstərir. Bu, hər biri dörd tam ədəd x_1, y_1, x_2 və y_2 ehtiva edən N sətiri ilə davam edir, hər birinin mütləq dəyəri 10000-dən yüksək deyil. Bu o deməkdir ki, bir xətt qalaktik xəritədə (x_1, y_1) və (x_2, y_2) nöqtələrini kəsir. Bu iki nöqtə eyni olmayacaq.
Çıxış verilənləri
Bütün müharibə ağalarını təmin etmək üçün bu təklifə əlavə etməli olduğunuz xətlərin sayını çıxış edin.