• 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 和 ⇐ 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)$ 与扫描线不平行的。

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

【此处应有图】