• Solved 6 out of 10 problems
• Rank 3 / 18
• Solved 7 out of 10 afterwards

(√ for solved, O for upsolved, - for tried but not solved)

这个东西直接按坐标枚举线跨过的格子即可。需要分斜率 $> 1$ 和 $\le 1$ 两类，注意 dx 和 dy 的符号。

这个题细节比较多。

看到这个题第一反应是拓扑学欧拉定理：

$$V+F-E=\chi$$

这个题里显然直线被多边形截得的部分与多边形本身构成一个连通图，那么 $\chi=2$。

多边形固有点数与固有边数都是 $N$。设新增点数 $\varDelta V$，新增边数 $\varDelta E$。

对上述公式进行代入并移项，得到：

$$F=(N+\varDelta E)+\chi-(N+\varDelta V)=\varDelta E-\varDelta V+2$$

那么最大化答案的过程就是最大化 $\varDelta E - \varDelta V$ 的过程。

如图，考察直线与多边形相交时对 $\varDelta E - \varDelta V$ 的贡献情况。

1. 直线与多边形的某边重合：$V+0, E+0$
2. 直线与多边形的某边相交：$V+1, E+1$
3. 直线过多边形的某点：$V+0, E+0$

上述三者对答案的贡献均为 $0$，那么多出来的答案就只可能由多边形截直线所得的线段贡献。

至此，可以发现这个题相当于最大化多边形截直线所得线段数。

考虑如何计算这个最大线段数。

每条截线段一定是由两个边夹着的。

所以一个直接的想法是直接统计每条边对应的斜率区间，然后求被覆盖次数最大的位置。

然后写了 WA7，想了想好像一个正方形就能叉掉（吃了不仔细看样例的亏，一开始就听队友的写扫描的方法就完了 2333）

然后乖乖的写扫描。容易发现只有在顶点处答案才会改变。考虑以下四种情况：

1. > 形，转过该斜率后答案 +1
2. > 形，到达该斜率时答案 +1
3. < 形，转过该斜率后答案 -1
4. < 形，到达该斜率时答案 -1

剩下的问题就是怎么确定多边形在我的哪一侧。

这个也好办，数分知识告诉我们，对于单连通区域，在边界上逆时针走的时候区域一定一直在左手侧，用叉积判一判即可。

写完发现倒在了样例 2，画出来发现是这么个东西：

提示我们处理顶点两侧有边与扫描线重合的情况。

类似上图右边这样一长串重合只有首尾弯走的情况，线扫过后答案只会 +1 而不会 +2。

那么我们对这样一串顶点，只能选择一个顶点计算贡献，否则会算重。如果不处理会漏算。

解决方案也好想，只处理一头就可以了，具体是哪一头则需要两种情况错开：

• 对 > 类顶点 $i$，我只处理 $(i-1, i)$ 与扫描线平行，$(i, i+1)$ 与扫描线不平行的。
• 对 < 类顶点 $i$，我只处理 $(i, i+1)$ 与扫描线平行，$(i-1, i)$ 与扫描线不平行的。

这样一来，以下几种情况的答案均可以准确计算，这个问题也就圆满解决了。

（图中绿色箭头代表扫描线方向，橙色箭头代表多边形顶点编号正序方向，红色点是纳入考虑的点，蓝色贡献是滞后生效，紫色贡献立即生效）

ptw：

• 不希望总是 cf 加训起飞，还剩两场牛客，加油！
• F 题应该多讨论讨论的，其实就是个比较难猜的结论。