#P17831. [Ontak2022]POL
[Ontak2022]POL
题目描述
给定一个凸多边形,其顶点按逆时针编号为 。
一次操作选择当前多边形上相邻的两个顶点 ,把 移到 并合并,代价为二者的欧氏距离。合并后保留顶点 的原编号,编号 消失。
你需要用恰好 次操作把多边形压缩为一个点。输入参数 决定任务:
- :求最小总代价。
- :输出一组达到最小总代价的操作。
输入格式
第一行一个整数 。第二行一个整数 ,表示测试组数,所有组使用相同的 。
每组先输入一个整数 ,随后 行每行两个整数 ,依次给出顶点。
输出格式
每组独立输出:
- 如果 ,输出一行最小总代价,建议至少保留10位小数。
- 如果 ,输出 行,每行两个原始编号 ,表示将当前顶点 移到相邻顶点 。
代价与标准最优值之差至多 即可;构造方案还必须使每一步操作合法。
数据范围
;每组 ;。所有坐标为整数,所有顶点互异,按逆时针顺序给出,保证多边形凸,但不要求严格凸,允许共线顶点。
子任务
| 子任务 | 附加限制 | 分值 |
|---|---|---|
| 1 | p=1,n≤7 | 4 |
| 2 | p=1,n≤15 | 8 |
| 3 | p=1,n≤50 | 12 |
| 4 | p=1,n≤100 | |
| 5 | p=1,n≤500 | |
| 6 | p=1,n≤2000 | 32 |
| 7 | p=2,n≤7 | 1 |
| 8 | p=2,n≤15 | 2 |
| 9 | p=2,n≤50 | 3 |
| 10 | p=2,n≤100 | |
| 11 | p=2,n≤500 | |
| 12 | p=2,n≤2000 | 8 |
样例 1
输入:
1
2
4
0 0
1 0
1 1
0 1
5
0 0
8 0
8 10
4 20
0 10
输出:
3.000000000000
36.770329614269
样例 2
输入:
2
2
4
0 0
1 0
1 1
0 1
5
0 0
8 0
8 10
4 20
0 10
输出:
3 2
4 1
2 1
4 3
5 3
3 2
2 1