BZOJ4948: [Wf2017]Airport Construction【线穿多边形】
题目描述:逆时针方向给出一个简单多边形,问内部可放置的线段的最长长度,保证无两边共线。n≤200n\le200n≤200题目分析:首先略加思考可以感觉到线段一定过多边形的某两个顶点,但线段的端点不一定是顶点,如下图:而且线段所在直线可能被多边形截成了几部分:所以需要枚举两个点,求出这条线与多边形所有边的交点,然后按坐标排序,然后将在多边形内部的连续线段考虑进答案。检验线段是否在多...