Casus şəbəkəsinin planı#9059
Conni qərargahda böyük bir xəritə tapdı. Bu xəritədə bir neçə nöqtə ya yaşıl, ya da qırmızı rənglə işarələnmişdi. Əvvəlcə bu tapıntıya çox əhəmiyyət vermədi, lakin sonradan məlum oldu ki, xəritə iki casus şəbəkəsinin yenidən qurulması layihəsini əks etdirir və bu layihələr fərqli rənglərlə göstərilib.
Yenidənqurma ideyası, agentləri müxtəlif nöqtələr arasında bölüşdürməkdən ibarətdir. Hər bir nöqtə birbaşa qərargah tərəfindən idarə olunur və hər nöqtədə bir neçə agent ola bilər. Belə hallarda, nöqtə xəritədə orada neçə agentin olması lazım olduğunu göstərən qədər dəfə işarələnir.
Nöqtələr tərəfindən idarə olunan ərazi belə müəyyən edilir: bu, müstəvidəki bütün nöqtələri əhatə edən ən kiçik sahəli konveks çoxluqdur. Əgər çoxluqdakı bütün nöqtələr bir düz xətt üzərində yerləşirsə, o zaman başlanğıc çoxluqdakı bütün nöqtələri əhatə edən ən kiçik uzunluqlu bu düz xəttin seqmenti idarə olunur.
Conni nöqtələrin yerləşdiyi yerləri dəqiq xatırlayırdı, lakin hansı nöqtələrin birinci layihəyə, hansının isə ikinciyə aid olduğunu xatırlaya bilmirdi. O, həmçinin xatırlayırdı ki, hər iki layihəni həyata keçirmək mümkün deyildi, çünki müxtəlif layihələrdən olan nöqtələrin idarə etdiyi ərazilər kəsişirdi.
Conni'nin xatırladığı son fakt isə bir rəngli nöqtələrin digər rəngli nöqtələrdən daha çox olması idi. Conni maraqlandı ki, nöqtələr layihələr arasında necə bölüşdürülə bilərdi. Formal olaraq, Conni nöqtələrin elə bir bölüşdürülməsini tapmaq istəyir ki, müxtəlif rəngli nöqtələrin idarə etdiyi ərazilər kəsişsin və müxtəlif layihələrə aid olan nöqtələrin sayı arasındakı fərq ən böyük olsun.
Birinci sətirdə n tam ədədi (4 ≤ n ≤ 10^5) - nöqtələrin sayı verilir. Növbəti n sətirdə xəritədə göstərilən nöqtələrin koordinatları olan iki tam ədəd x[i] və y[i] (-10^9 ≤ x[i], y[i] ≤ 10^9) verilir. Axtarılan bölüşdürülmənin mövcud olduğu təmin edilir.
Birinci sətirdə m tam ədədini - kiçik ölçülü nöqtələr çoxluğunun ölçüsünü çıxarın. İkinci sətirdə bu çoxluğa daxil olan nöqtələrin indekslərini - m ədədini çıxarın. Əgər optimal cavablar bir neçədirsə, istənilənini çıxarmağa icazə verilir.
Nümunə 1