#P2477. [SCOI2008] 套圈

    ID: 1485 远端评测题 1000ms 125MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>各省省选四川2008期望动态规划dp状态压缩状压

[SCOI2008] 套圈

题目背景

四川2008NOI省选

题目描述

平面上有n个点,你的任务是用k个圆圈把它们套住。换句话说,这n个点

中的每个点都必须在某个圆的内部或者边界上。这k 个圆半径必须都是不超过

106的正整数,且它们的总面积应尽量小。

输入格式

本题是提交答案题目,输入文件circle1.in~circle10.in已经放在用户目录中。

输入第一行包含两个正整数n 和k。以下n 行每行两个不超过106的非负整数,

即每个点的坐标。

输出格式

本题是提交答案题目,输出文件circle1.out~circle10.out 应放在用户目录中。

输出恰好k行,每行三个整数x, y, r,即圆心坐标和半径。圆心坐标必须为不超

过106的非负整数,而半径是不超过106的正整数。

3 1
1 0
0 1
1 1
1 1 1