uoj#P389. 【UNR #3】白鸽

【UNR #3】白鸽

在咕了无数锅和 ddl 之后,S***pe 终于如愿以偿,变成了一只翱翔在天空中的白鸽。S***pe 很久以前听说过,白鸽的使命,就是以不同的方向飞过天空,带给地上的人们无尽的灵感。可是刚刚被变成白鸽的 S***pe 心理并不平衡,他远远地看见了地面上那个甩锅给他的人 w*x,他决定不给 w*x 提供应该提供的灵感,而且 S***pe相信不给灵感的方法就是绕着 w*x 顺时针转圈,这样的话对于 w*x 来说白鸽就只有往右侧飞行,而不能看到白鸽以不同的方向飞过天空了。

S***pe 觉得自己的行程必须经过若干个关键点,他请你帮他规划路线。

简而言之,现在在二维平面上,有一个给定一张 $n$ 个点 $m$ 条边的无向图作为线路,保证无自环。点从 $1$ 开始编号。

在这张图上的每个节点都在二维平面上有自己的坐标,而一条边对应了连接这两个点的线段,S***pe 的目标是从 $1$ 号点开始飞行,每次沿着一条线段到达一个新的点,循环往复最后停在 $1$ 号点,且经过每条线段恰好一次。同时你需要最大化围绕原点顺时针旋转的次数。

顺时针旋转的次数:假设 w*x 在 S***pe 飞行的过程中始终保持正面朝向 S***pe,那么在 S***pe 结束飞行之后 w*x 原地右转的圈数就是顺时针旋转的次数(可以为负)。

如果无解输出 $-1$。保证没有两个点重合,没有点和原点重合,且没有两个点所确定的直线经过原点。

输入格式

第一行两个正整数 $n, m$ 分别表示这张无向图的点数和边数。

接下来 $n$ 行每行两个整数 $x_i, y_i$ 表示第 $i$ 个点的坐标。

接下来 $m$ 行每行两个整数 $u_i, v_i$ 表示从点 $u_i$ 到点 $v_i$ 之间有一条无向边。

输出格式

一行一个整数,如果是 $-1$ 表示无解,否则表示最大的旋转次数。

5 10
1 9
6 -8
9 7
-5 -10
10 -6
1 3
3 4
2 3
1 4
5 2
4 5
1 3
3 1
4 1
3 1
2

explanation

样例中的图如下图所示,注意图中的重边未被标识。

样例一解释

一种最优的遍历顺序是:

$1 \rightarrow 3 \rightarrow 2 \rightarrow 5 \rightarrow 4 \rightarrow 1 \rightarrow 3 \rightarrow 4 \rightarrow 1 \rightarrow 3 \rightarrow 1$

再次提醒:注意重边。

3 5
-764351767 899476675
103147230 -443149366
432530806 578822602
2 3
2 3
1 3
3 1
2 3
-1

explanation

不存在满足条件的路径。

样例三

见样例数据下载。

样例四

见样例数据下载。

限制与约定

对于所有数据,$1 \le n, m \le 2 \times 10^{4}$,$|x_i|, |y_i| \le 10 ^ 9$,$1 \le u_i, v_i \le n, u_i \ne v_i$。

子任务分值限制
1$15$$n, m \le 10$
2$15$$n, m \le 20$
3$20$$n, m \le 100$
4$20$$n, m \le 5000$
5$30$$n, m \le 2 \times 10 ^ 4$

时间限制:$1\texttt{s}$

空间限制:$256\texttt{MB}$

下载

样例数据下载