[POJ 3130]

How I Mathematician Wonder What You Are!

判断多边形内核。

题意为N个顶点逆时针顺序描述的一个多边形,要求判断该多边形是否有“内核”。所谓“内核”,就是在该多边形内的一块区域,站在这块区域内任意一点观察多边形的内部,都可以无死角地看遍整个多边形。

解这题涉及到半平面的概念。其实就是每条线段都会将平面区域划分成两部分,一部分包含多边形内部,一部分不包含。那么,将所有线段对应的包含多边形内部那一半的平面区域求交集,就得到了多边形的内核(如果存在)或者空集(不存在内核)。

进一步考虑实现问题的话,可以将每条直线描述为ax+by+c=0,那么半平面方程即为ax+by+c>=0,其中a、b、c三个系数,根据直线的朝向以及题目给定的逆时针顺序,a是取-1或1的,进而可以确定b和c。多边形的内核区域,可以抽象为某些点,进一步分析可以发现,若存在内核,则其角一定是某两条边所在直线的交点。由于最多只有50条边,那么可以枚举n(n-1)/2个交点,依次代入n个半平面方程,看是否存在点满足对所有半平面方程都大于0即可。

最近都在练习计算几何的题目。感觉这类题有个特点是比较偏数学公式的推导,对复杂度的要求不会太高。

借这个机会好好复习下各种几何工具吧。