C. Эдо ба Соронз

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

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

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

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

Эдод $n$ ширхэг хөргөгчний соронзны цуглуулга байгаа.

Тэр хөргөгч худалдаж авч соронзнуудыг хаалган дээр нь тогтоохоор шийдсэн. Дэлгүүр дараах хязгаарлалтуудыг хангах дурын хэмжээтэй хаалгатай хөргөгчийг хийж чадна: хөргөгчний хаалга тэгш өнцөгт хэлбэртэй байх ёстой, хаалганы урт болон өргөн хоёулаа эерэг бүхэл тоон утга байна.

Эдо хөргөгчин дээр соронзуудаа хэрхэн байрлуулахыг хүсэж буйгаа зурсан. Тэр соронз бүрийг координатын тэнхлэгүүдтэй параллель талуудтай тэгш өнцөгтөөр илэрхийлсэн хавтгай дээрх координатуудын системийг танилцуулсан.

Одоо тэр $k$-с илүүгүй тооны соронзыг (тэр бүгдийг нь үлдээж ч болно) арилгах ба үлдсэн бүх соронзыг хөргөгчний хаалган дээр тогтоох ба хаалганы талбай боломжит хамгийн бага байх хэрэгтэй. Хэрвээ соронзны төв нь хөргөгчний хаалган дээр эсвэл түүний хүрээн дээр байвал хаалган дээр тогтоогдсон гэж үзнэ. Үлдсэн соронзнуудын харьцангуй байрлалууд нь төлөвлөгөөтэй харгалзах ёстой.

Бидэнд сүүлийн хоёр өгүүлбэрийг тайлбарлахыг зөвшөөрнө үү. Бид хоёр соронзыг хөргөгчин дээр тогтоох гэж байна гэж үзье. Төлөвлөгөөн дээрх соронзны зүүн доод булангийн координат нь ($x_{1}$, $y_{1}$) ба баруун дээд булангийн координат нь ($x_{2}$, $y_{2}$) байвал үүний төв нь (, ) (бүхэл тоонууд биш байж болно) дээр байна. Харьцангуй байршил нь төлөвлөгөөтэй харгалзаж байх ёстой гэдэг нь зөвхөн боломжит үйлдэл хөрвүүлэгдэх буюу анхны төлөвлөгөөн дээр байсан хоёр соронзны төвүүдийг холбосон вектор нь хөргөгчин дээр байгаа тэр хоёр соронзны төвүүдийг холбосон вектортой тэнцүү байх ёстой.

Хөргөгчний хаалганы талууд ч мөн адил координатын тэнхлэгүүдтэй параллель байх ёстой.

Оролт

Эхний мөрөнд хоёр бүхэл тоон утга $n$ ба $k$ ($1 ≤ n ≤ 100 000$, $0 ≤ k ≤ min(10, n - 1)$) байх ба Эдод байгаа соронзны тоо ба Эдо хөргөгчин дээр байрлуулахгүй байх соронзны хамгийн их тоо юм.

Дараагийн $n$ мөрөнд соронзнуудыг байрлуулах анхны төлөвлөгөөг тодорхойлно. Мөр бүрт дөрвөн бүхэл тоон утга $x_{1}, y_{1}, x_{2}, y_{2}$ ($1 ≤ x_{1} < x_{2} ≤ 10^{9}$, $1 ≤ y_{1} < y_{2} ≤ 10^{9}$) байх ба тухайн соронзны зүүн доод болон баруун дээд булангуудын координатууд юм. Соронзнууд зарим хэсгээрээ давхцаж болох ба бүхлээрээ ч давхцаж болно.

Гаралт

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

Орчуулсан: Г.Мэндбаяр

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

Оролт
3 1
1 1 2 2
2 2 3 3
3 3 4 4
Гаралт
1
Оролт
4 1
1 1 2 2
1 9 2 10
9 9 10 10
9 1 10 2
Гаралт
64
Оролт
3 0
1 1 2 2
1 1 1000000000 1000000000
1 3 8 12
Гаралт
249999999000000001

Тэмдэглэл

Эхний жишээн дээр эхний эсвэл гурав дахь соронзыг арилгах нь хамгийн тохиромжтой юм. Хэрвээ бид эхний соронзыг арилгах юм бол үлдсэн хоёрынх нь төв (2.5, 2.5) ба (3.5, 3.5) цэгүүд дээр байрлана. Ингээд харгалзах талбай нь нэгтэй тэнцүү байх 1 өргөнтэй, 1 өндөртэй хаалгатай хөргөгч худалдаж авахад хангалттай.

Хоёр дахь жишээн дээр ямар ч соронзыг арилгасан хариулт өөрчлөгдөхгүй буюу бидэнд 8 өргөнтэй 8 өндөртэй хаалгатай хөргөгч хэрэгтэй.

Гурав дахь жишээн дээр та юуг ч арилгаж чадахгүй буюу $k = 0$.

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