[HNOI 2016] 矿区

[HNOI 2016] 矿区 平面图转成对偶图,对偶图随便建棵生成树,求出来以每个节点为根的子树中的所有区域的面积之和,然后对于每组询问,沿着边走一遍,加加减减搞一搞就行了

[HNOI 2019] 鱼

LOJ #3054. 首先枚举一个点$D$,然后将所有点按与$D$的连线的角度排序,枚举点$A$,随着角度增大,可以用双指针维护一下当前鱼尾的范围,求出鱼尾的方案数。鱼身的$BC$显然被$AD$垂直平 […]

[JSOI 2018] 战争

Luogu P4557 首先这两个部落很显然就是两个凸包。我们要解决的就是凸包$B$在沿着给出的向量$x$平移之后与凸包$A$是否有交,即是否存在凸包$A$中的一点$a$和凸包$B$中的一点$b$,使 […]

[HNOI2007]最小矩形覆盖

Luogu P3187 思路 垃圾题目,卡我精度 首先,对于所有点搞出一个凸包。很显然,答案矩形一定有一条边和凸包的一边重合。那么只要找出落在矩形另外三边上的点,就可以确定答案矩形了。只要枚举当前边, […]