【BZOJ2618】【CQOI2006】凸多边形

半平面交还是要了结一下的。。

LXK买的书真是不错 什么都有模板蒯。。将点转为complex运算实在巧妙 不用自定义struct了

于是重写了一遍

这次的裸题是求两个凸多边形的交,也就是把每个凸多边形拆成一堆半平面直接套

不过要求面积。。于是就要把半平面交上的点算出来并且算面积

任意凸多边形的面积公式:

$$S=\frac{1}{2}\sum_{i=1}^{n}|\overrightarrow{OP_i}\times \overrightarrow{OP_{i+1}}|(P_{n+1}=P_1)$$

求两条直线A、B的交点坐标公式(已知直线上两点):

$$S_1=\overrightarrow{A_1 A_2}\times \overrightarrow{A_1 B_1}$$

$$S_2=\overrightarrow{A_1 B_2}\times \overrightarrow{A_1 A_2}$$

$$P=B_1+\frac{S_1}{S_1+S_2}(B_2-B_1)$$

(应该没打错吧)

另外有关<complex>库的函数:

a.real() a的实部
a.imag() a的虚部
conj(a) a的共轭复数,即将虚部变为相反数
arg(a) a的辐角(打表发现从x轴负半轴逆时针递增。。(没学过复数只能这么玩了))

最后就是贴代码了← ←

说点什么

  Subscribe  
提醒