POJ2398计算几何、叉积判断点在线段左/右侧
题目
二维平面中有一个矩形,放入n块隔板,将矩形分成n+1个区域,隔板保证不相交且两端点在矩形的两条横向线段中。形如下图:
给出m个点,求包含t个点的区域数量。
求解思路
可以用叉积判断一个点在线段的左侧还是右侧。
$\vec{OA} \times \vec{OB}=|OA|\times|OB|\times \sin\theta$
叉积为负,说明$\theta 大于\pi$
如果$\vec{OA} \times \vec{OB} >0$ 并且 $\vec{OC} \times \vec{OD}<0$,说明点O在区域ABCD内。
代码
1 |
|