... 平面内给定 n 条直线,求封闭区域的个数以及它们的面积.
(注意代码这里我禁止向顺时针方向转移,如果允许.那么会顺时针方向会多分割出一个包含所有这些极小封闭区域的大封闭区域.
(.补充说明一下精度问题.这个真是折磨死人了.当然最可靠方法还是是用分数的形式保存每个 double.
这样的话中间对每个算式除的地方都乘上来.这样虽然安全有效但是改累死了.
后来发现其实别的地方有 bug 而已.总之生卡精度的题其实还是没有的吧?WA 的话可能还是别的其他的地方写疵了.
一个国家有 n 个城市,且城市之间的道路形成一棵树,现在要求划分出若干个省,使得每个省的城市数目属于 [B 3B].
并为每个省指定一个省会,使得属于该省的所有城市,都可以在该省内部的范围内到达省会.
那么把它们合并成若干 [B 2B] 之间的点集,并以 u 点作为省会.剩下来的点集数目+上 u 点自己一定不超过 B.
最后会剩下与根节点相连的不超过 B 个点的集合,任选一个与该集合相邻的集合与之合并即可.
这样除了与根结点相连的这个点集外,其他点集的大小都是 [B 2B] 之间.