E. Харуулын цамхаг

хугацааны хязгаарлалт 1.5 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Алс холын хаант улсад нэгэн маш шунахай хаан амьдардаг байжээ. Тэрээр газар нутгаа хамгаалахын тулд $n$ харуулын цамхаг барьсан. Харуулын цамхгаас гадна 2 арми байдаг ба тус бүрийг нь эзэрхэг түрэмгий генералууд удирддаг. Генералууд нэг нэгэндээ тохирдоггүй ба тэд хэзээ ч нэг цамхаг дээр 2 армийн цэргүүдийг зэрэг зогсохыг зөвшөөрдөггүй.

Харуулын цамхаг бүрд аль нэг генерал өөрийнхөө армийн хэсэг цэргүүдийг илгээх ёстой. Цамхгийг удирдахдаа генерал тус бүр хаанаас цалин хүсжээ. Тэд үнэхээр алс холын хаант улсад амьдардаг тул генерал бүр өөрсдийнхөө цалинг дараах өвөрмөц аргаар үнэлжээ: тэр өөрийнх нь армийн цэргүүд байрласан хамгийн хол зайтай 2 цамхгийг олоод энэхүү зайтай тэнцүү хэмжээний цалин хүсжээ. Энэ улсад цамхаг бүр хавтгайд $(x, y)$ координаттай цэгээр дүрслэгдсэн ба $(x_{1}, y_{1})$ ба $(x_{2}, y_{2})$ координаттай 2 цэгийн хувьд хоорондох зайг нь $|x_{1} - x_{2}| + |y_{1} - y_{2}|$ гэж тодорхойлжээ.

Шунахай хаан генералуудын тавьсан шаардлагад яг ч сэтгэл хангалуун биш байсан тул 2 генералын шаардсан цалингийн ихтэй нь тэнцэх хэмжээний цалинг дунд нь өгөхийг л зөвшөөрсөн. Гэсэн хэдий ч хааны сэтгэл ханахгүй байсан тул цамхгуудыг 2 армийн хооронд зохион байгуулах бүх боломж дотроос хамгийн хямд нэгийг нь олохыг хүссэн. Цамхаг бүрийг яг нэг армийн цэргүүдээр эзлүүлэх ёстой.

Тэр энэ ажлыг гүйцэлдүүлэхийн тулд таныг хөлслөв. Та цалинг өгөхөд хангалттай байх мөнгөний доод хэмжээг олох ёстой. Мөн хаан маш нягт нямбай байдаг шиг та ийм хэмжээний үнэтэй байхаар зохион байгуулах боломжийн тоог олох ёстой. Энэ тоо нь маш том тоо байж болох тул хаанд $10^{9} + 7$ -д хуваахад гарах үлдэгдлийг нь л мэдэхэд хангалттай.

Хэрэв эхний генералын цэргүүдийн эзэлсэн цамхгуудын багц нь ялгаатай байвал хоёр зохион байгуулалтыг ялгаатай гэж үзнэ.

Оролт

Эхний мөрөнд бүхэл тоо $n$ ($2 ≤ n ≤ 5000$) өгөгдөнө, $n$ нь харуулын цамхгийн тоо. Дараах $n$ мөрөнд, тус бүр 2 бүхэл тоо $x, y$ -- $i$-р цамхгийн координат $(0 ≤ x, y ≤ 5000)$. Аль ч хоёр цамхаг нэг цэг дээр оршихгүй.

Pretest 6 нь энэ бодлогын хамгийн том тестийн нэг болно.

Гаралт

Эхний мөрөнд генералуудад өгөхөд хангалттай байх мөнгөний доод хэмжээг хэвлэ.

Хоёрдох мөрөнд хамгийн бага мөнгө шаардагдах зохион байгуулалтын тоог хэвлэ. Энэ тоог $1000000007$ ($10^{9} + 7$) модулиар тооцоол.

Орчуулсан: Б.Алтангэрэл

Жишээ тэстүүд

Оролт
2
0 0
1 1
Гаралт
0
2
Оролт
4
0 0
0 1
1 0
1 1
Гаралт
1
4
Оролт
3
0 0
1000 1000
5000 5000
Гаралт
2000
2

Тэмдэглэл

Эхний жишээн дээр зөвхөн 2 цамхаг байх ба хоорондох зай нь 2 байна. Хэрэв бид хоёуланг нь нэг генералд өгвөл 2 хэмжээний мөнгө төлөх хэрэгтэй болно. Хэрэв генерал бүрд нэг нэгийг өгвөл цалин нь 0 болно. Энэ нь байж болох хамгийн бага цалин юм. Мөн үүнийг 2 янзаар авч болохыг бид амархан харж чадна.

Сэтгэгдлүүдийг ачааллаж байна...