> rt
题意：已知一个多边形的n个顶点坐标，然后再给一个钉子，给定钉子的半径和圆心坐标，首先判断多边形是否为凸多边形，若为凸多边形，再判断钉子是否可以放到凸多边形内部。
 
思路：很好的计算几何。
1.由于顶点给出的顺序可能为逆时针或顺时针，所以在判断是否为凸边变形，利用叉积的性质，每个点依次扫描看是否都顺着同一的方向转动。
2.判断圆(钉子)是否在多边形内部，第一步判断圆心是否在凸多边形内部（以圆心为定点扫描一周），第二步再判断圆心到某一边的最短距离，若存在某最短距离大于圆心，则圆不能放在凸多边内。

• Re:谁能说一下这道题的题意？ (268) xieweibbz 2012-03-31 20:00:41