本题翻译(新)
查看原帖
本题翻译(新)
1085667
KohaD_SEGA楼主2025/6/30 00:12

显然,本题的原翻译极其粗糙,包括甚至使用“看不太懂”等不负责任的用语。以下为本题正确的简略翻译。


题目描述

我们要在一个平面上为一组坐标围起一个最短周长的篱笆,也就是构造这些点的凸包。如果坐标去重后只有一个点,则周长为 00.

输入格式

第一行为一个整数 T (T100)T\ (T\leqslant 100) 表示测试用例的数量。

对于每个数据,第一行为 n (n105)n\ (n\leqslant 10^5) 表示当前测试用例中点的数量。以下 nn 行,第 kk 行为 kk 号点的坐标。

输出格式

o                    // 凸包的周长,保留两位小数
p1 p2 ... pk         // 构成凸包的点的编号
[空行]
[下一个测试用例的输出] ...

输出要求细节:

输出构成凸包的点的编号必须从最下边(yy 最小)的点开始。如果有多个最下的点,则在其中从最左边(xx 最小)的点开始。然后,逆时针输出凸包上的点。

如果有几个点位于同一处且该点参与了凸包的构成,只输出编号最小的点。

说明/提示

对于100%的数据,104xi, yi104-10^4\leqslant x_i,\ y_i\leqslant 10^4

2025/6/30 00:12
加载中...