Problem
Çiftçi John'un inekleri farklı noktalarda (x1,y1)…(xn,yn) ) alanları (1≤N≤100.000, tüm xi ve yi 1.000.000'i aşmayan pozitif tek tam sayılardır. FD, alanını sonsuz bir çitle bölmek istiyor x=a denklemiyle tanımlanan kuzeyden güneye uzunluk (a çift bir tamsayıdır, bu nedenle çitin herhangi bir ineğin konumundan geçmemesi sağlanır.) Ayrıca sonsuz uzunlukta bir çit yapmak istiyor. doğudan batıya, y=b denklemiyle tanımlanır, burada b bir çift tamsayıdır Bu iki çit (a,b) noktasında kesişir ve birlikte alanı dört bölgeye ayırır.
FD, a ve b'yi "dengeli" olacak şekilde seçmek istiyor tüm bölgelerdeki inek sayısı, yani böylece çok fazla inek içeren bir bölge yoktur. Bu dört bölgedeki maksimum inek sayısı M olsun, FD M'nin mümkün olduğu kadar küçük olmasını istiyor. FD'nin M için mümkün olan bu minimum değeri belirlemesine yardımcı olun.
GİRİŞ BİÇİMİ:
Girişin ilk satırı bir tam sayı, N içerir. Sonraki n satırın her biri, x ve y koordinatlarıyla gösterilen bir ineğin konumunu içerir.
ÇIKTI BİÇİMİ:
Çitlerin optimum düzeniyle PD'ye ulaşabilecek minimum olası M değerini yazdırın.
|
Gir |
Çıktı |
|
7
73
5 5
7 13
3 1
117
5 3
9 1
|
2 |