E. Хавтгай дээрх хоёртын мод

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

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

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

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

Үндэстэй мод гэдэг нь нэг оройноос (үндэс) бусад орой руу яг нэг замаар очиж болдог, ямар нэг цикл агуулаагүй чиглэлт граф юм.

Орой бүрээс хамгийн ихдээ хоёр ирмэг гарсан үндэстэй модыг хоёртын мод гэнэ.

Хавтгай дээр бүх ирмэгүүд нь дээрээс доошоо чиглэсэн хоёртын мод зурсан байна. Энэ нь $u$-с $v$ рүү чиглэсэн ирмэг бүр нь $y_{u} > y_{v}$ нөхцлийг хангасан байна гэсэн үг.

Модны бүх оройн координат өгөгдсөн бол хоёртын үндэстэй мод үүсгэж байхаар оройнуудыг ирмэгээр холбох ба ирмэгүүдийн нийт урт нь аль болох бага байх ёстой. Бүх ирмэгүүд дээрээс доош чиглэсэн байх ёстойг анхаараарай.

Оролт

Эхний мөр нь модны ирмэгүүдийн тоо болох $n$ ($2 ≤ n ≤ 400$) бүхэл тоог агуулна. Дараа нь $n$ мөрүүд байх ба мөр бүрт $x_{i}, y_{i}$ ($|x_{i}|, |y_{i}| ≤ 10^{3}$) тоонууд байна. Эдгээр нь оройн координатууд юм. Бүх цэгүүд заавал ялгаатай байх ёстой.

Гаралт

Өгөгдсөн цэгүүдээр хоёртын үндэстэй мод үүсгэх боломжгүй бол "-1" гэж хэвлэнэ. Эсрэг тохиолдолд нэг бодит тоо хэвлэнэ. Энэ нь хоёртын модны ирмэгүүдийн хамгийн бага нийт урт юм. Абсолют буюу харьцангуй алдаа нь $10^{-6}$-ээс хэтрэхгүй бол хариултыг зөв гэж үзнэ.

Орчуулсан: Даариймаа

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

Оролт
3
0 0
1 0
2 1
Гаралт
3.650281539872885
Оролт
4
0 0
1 0
2 1
2 0
Гаралт
-1
Сэтгэгдлүүдийг ачааллаж байна...