#P17831. [Ontak2022]POL

    ID: 16774 传统题 500~5000ms 512MiB 尝试: 1 已通过: 1 难度: 7 上传者: 标签>计算几何图论贪心CF2200最小生成树算法基础模拟

[Ontak2022]POL

题目描述

给定一个凸多边形,其顶点按逆时针编号为 1,2,…,n1,2,\ldots,n。

一次操作选择当前多边形上相邻的两个顶点 A,BA,B,把 AA 移到 BB 并合并,代价为二者的欧氏距离。合并后保留顶点 BB 的原编号,编号 AA 消失。

你需要用恰好 n−1n-1 次操作把多边形压缩为一个点。输入参数 pp 决定任务:

  • p=1p=1:求最小总代价。
  • p=2p=2:输出一组达到最小总代价的操作。

输入格式

第一行一个整数 p∈{1,2}p\in\{1,2\}。第二行一个整数 tt,表示测试组数,所有组使用相同的 pp。

每组先输入一个整数 nn,随后 nn 行每行两个整数 xi,yix_i,y_i,依次给出顶点。

输出格式

每组独立输出:

  • 如果 p=1p=1,输出一行最小总代价,建议至少保留10位小数。
  • 如果 p=2p=2,输出 n−1n-1 行,每行两个原始编号 Aj,BjA_j,B_j,表示将当前顶点 AjA_j 移到相邻顶点 BjB_j。

代价与标准最优值之差至多 10−410^{-4} 即可;构造方案还必须使每一步操作合法。

数据范围

t≤5t\le5;每组 n≤2000n\le2000;∣xi∣,∣yi∣≤106|x_i|,|y_i|\le10^6。所有坐标为整数,所有顶点互异,按逆时针顺序给出,保证多边形凸,但不要求严格凸,允许共线顶点。

子任务

子任务 附加限制 分值
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