F.Nezzar and Nice Beatmap
生肉{:target=”_blank”}
题目翻译
在一个二维平面上有 $n$ 个互不相同点 $A _ 1, A _ 2, \cdots, A _ n$。
$\text{Nezzar}$ 想知道,是否存在一个 $1 \sim n$ 的排列 $p _ 1, p _ 2, \cdots, p _ n$,使得我们依次连接 $A _ {p _ 1}, A _ {p _ 2}, \cdots, A _ {p _ n}$ 后,图形中每个以 $A _ i$ 为顶点的角度,都严格小于 $90$ 度。
换句话说,是否存在一个 $1 \sim n$ 的排列 $p _ 1, p _ 2, \cdots, p _ n$,使得 $\forall 1 < i < n$,都有 $\angle A _ {i - 1} A _ i A _ {i + 1} < 90 ^ \circ$。
输入
第一行一个整数 $n \ (3 \leq n \leq 5000)$。
接下来 $n$ 行,每行两个整数 $x _ i, y _ i \ (- 10 ^ 9 \leq x _ i, y _ i \leq 10 ^ 9)$,表示 $A _ i$ 的坐标。
数据保证所有点的坐标互不相同。
输出
如果排列不存在,输出 -1
。
否则输出 $n$ 个整数,表示排列 $p$。
如果存在多组解,输出任意一组解即可。
样例输入
5
0 0
5 0
4 2
2 1
3 0
样例输出
1 2 5 3 4
样例解释
按样例输出中的排列,依次连接所有点后,应得到如下图形:
该图中每个形成的每个角的度数都严格小于 $90 ^ \circ$。
请注意,$\angle A _ 1 A _ 2 A _ 5$ 是 $0 ^ \circ$,而 $\angle A _ 1 A _ 5 A _ 2$ 是 $180 ^ \circ$。
算法
(暴力枚举) $O(n^2)$
我们可以仿照求凸包的算法,按顺序从 $A _ 1$ 到 $A _ n$ 依次考虑所有点。
假设我们已经考虑了前 $k$ 个点,并确定了这 $k$ 个点排列 $p _ 1, p _ 2, \cdots, p _ k$,现在我们要在 $A _ {p _ 1} \sim A _ {p _ k}$ 中加入 $A _ {k + 1}$。
我们可以将 $A _ {k + 1}$ 先放入 $A _ {p _ k}$ 后,即让 $p _ {k + 1} = k + 1$,然后判断 $A _ k$ 这个点是否合法,即是否 $\angle A _ {p _ {k - 1}} A _ {p _ k} A _ {p _ {k + 1}} < 90 ^ \circ$。
如果 $\angle A _ {p _ {k - 1}} A _ {p _ k} A _ {p _ {k + 1}} < 90 ^ \circ$,则继续考虑 $k + 2$,以此类推。
考虑 $\angle A _ {p _ {k - 1}} A _ {p _ k} A _ {p _ {k + 1}} \geq 90 ^ \circ$ 的情况:
做法:若 $\angle A _ {p _ {k - 1}} A _ {p _ k} A _ {p _ {k + 1}} \geq 90 ^ \circ$,直接交换 $p _ {k + 1}, p _ k$,再往前考虑 $p _ {k - 2}, p _ {k - 1}, p _ k$ 是否合法。
证明:
其实贴张图就一目了然了
交换 $p _ {k + 1}, p _ k$ 后,原来的角变成了 $\angle A _ {p _ {k - 1}} A _ {p _ {k + 1}} A _ {p _ k}$。
因为 $\angle A _ {p _ {k - 1}} A _ {p _ k} A _ {p _ {k + 1}} \geq 90 ^ \circ$,所以 $\angle A _ {p _ {k - 1}} A _ {p _ {k + 1}} A _ {p _ k} < 90 ^ \circ$。
那么证明就证完了。
所以我们这个做法是正确的。
至于具体怎么判断某个角的度数,直接套计算几何的板子就可以了。
时间复杂度
最坏情况下,对于每个点,我们都会遍历它前面的所有点,复杂度为 $O(n ^ 2)$。
听说这题好像有 $O(n \log n)$ 排序做法?
C++ 代码
#include <cmath>
#include <cstdio>
#include <cstring>
using namespace std;
const double eps = 1e-10;
struct Point
{
double x, y;
double len() {return hypot(x, y);}
Point nrm() {return (Point) {x / len(), y / len()};}
Point operator + (const Point& t) {return (Point) {x + t.x, y + t.y};}
Point operator - (const Point& t) {return (Point) {x - t.x, y - t.y};}
Point operator * (const double& t) {return (Point) {x * t, y * t};}
Point operator / (const double& t) {return (Point) {x / t, y / t};}
double operator * (const Point& t) {return x * t.y - y * t.x;}
double operator & (const Point& t) {return x * t.x + y * t.y;}
};
int sgn(double x)
{
if (fabs(x) < eps) return 0;
if (x < 0) return -1;
return 1;
}
int dcmp(double a, double b)
{
if (fabs(a - b) < eps) return 0;
if (a < b) return -1;
return 1;
}
// 返回cos角abc
double angle(Point a, Point b, Point c)
{
c = c - b, a = a - b;
return (a & c) / a.len() / c.len();
}
/*****以上是计算几何板子*****/
const int N = 5005;
int n, p[N];
Point a[N];
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i ++ ) scanf("%lf%lf", &a[i].x, &a[i].y);
p[1] = 1, p[2] = 2;
for (int i = 3; i <= n; i ++ )
{
p[i] = i;
for (int j = i; j >= 3; j -- )
if (sgn(angle(a[p[j - 2]], a[p[j - 1]], a[p[j]])) <= 0)
swap(p[j], p[j - 1]);
}
for (int i = 1; i <= n; i ++ ) printf("%d ", p[i]);
return 0;
}
$$ $$
UPD: 代码不知道为啥又被卡常了。。明明以前都过了的。。链接{:target=”_blank”}
关于卡常:
struct Point
里面有很多没用到的函数,把那些函数都删掉就可以了。
AC Code{:target=”_blank”}
代码好像在cf上会t掉?
已更新~