Task: Relay

题目翻译

有一座岛屿，旁边有若干条船。每当有一条船遇难，他就会给其他船发出“Mayday”信号，每个接到"Mayday"信号的船会向其他船发出"Relay"信号。两个船可以通信当且仅当两个船所在位置连线不穿过岛屿。岛屿可以近似为一个凸多边形，船可以近似为一个点。现在遇难的船为1号船，问有多少个船接收到了"Relay"信号或者"Mayday"信号。

船的数量、描述岛屿的凸多边形点数均 \(\le 10^5\)。

提交地址

https://www.luogu.com.cn/problem/U153541

题解

基本想法

首先考虑一个船可以向哪些船传达信号。考虑这个船给这个凸多边形做切线。

点A对凸多边形切线这样定义：A与凸多边形上一点连成的线与凸多边形没有交点。

如果A与凸多边形相切于点X与Y，那么有AX外和AY外还有XY外的点都可以被A看到。

如何求切线？考虑到如果A切多边形于点B，设其两边的点为C和D，那么必有 AC转到AB是逆时针 与 AB转到AD是逆时针 正确性不同。所以可以有一种 \(\mathcal O(n)\) 求切线的做法。

那么剩下的问题是处理收到"Relay"信号的船。考虑只要找到到两个“最靠边”的点，就可以给所有收到"Relay"信号的点发送信号了。所以只要找到最靠边的点即可。所谓最靠边的点，有两个限制：

1. 切多边形的位置要尽量靠后。


2. 切线与多边形的夹角尽量大。

（叙述不是很严谨）

考虑这样：每个点尝试向后推切线的位置，推不动就停止。这样复杂度是经过的节点数和经过的切线数量，是正确的。

然而这些思路都很好想，但是有一个非常重要的问题就是千万不要用解析几何实现！！！要不然需要分类讨论一坨稀屎。

计算几何实现

如果要判断顺时针还是逆时针，可以考虑使用向量的叉积。如果 \(a\) 与 \(b\) 的叉积为正，那么 \(a\) 转到 \(b\) 就是逆时针转，。否则就是顺时针。如果 \(a\) 的坐标定义为 \((x_1,y_1)\) ，\(b\) 的坐标定义为 \((x_2,y_2)\) ，那么 \(a\times b=x_1y_2-x_2y_1\) 。可能为一的核心就这一个吧。

代码

https://paste.ubuntu.com/p/qzkwTTq3FN/

写的时候注意画出来看看嗷！