链接：

Airport Construction

题意：

逆时针给一个简单多边形(不一定为凸多边形)的每一条边，问内部可放置的最长线段的长度。数据保证无两条边共线。

思路：

首先，由于不一定是凸多边形，直接用凸包旋转卡壳求直径方法是不对的。

考虑最长的线段何时取到：假设线段不过两个顶点，其长度总可以通过继续旋转线段使其碰到顶点而继续增大。由反证法可证线段一定过两个顶点。那么线段端点一定为顶点吗？不一定。

上图即是一个反例。

考虑到点的个数<=200，这个规模O(n^4)复杂度可能都不会TLE，自然想到枚举多边形的每两点，连成直线，求直线在多边形内连续的每条线段，更新答案。

问题转化为怎样求直线被多边形切后的连续线段长度。可以采用多边形与直线的交点作为切分点，求每个切分点之间的线段。

由于边以逆时针顺序给出，故可判断每条边的两端点和直线的位置关系。若两点在直线异侧或者一点在直线上，则此边将直线切断，交点作为切分点；若两点在直线同侧，无任何影响；若两点均在直线上，相当于在直线上多了两个切分点。在得到一系列切分点之后，根据坐标排个序，遍历判断相邻切分点之间的每条线段在多边形内还是多边形外，如果在多边形内，局部答案加上这条线段长度，如果在多边形外，更新全局答案，局部答案清零。

附：官方题解

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
static const int maxn = 100010;
static const int INF = 0x3f3f3f3f;
static const int mod = (int)1e9 + 7;
static const double eps = 1e-8;
static const double pi = acos(-1);

void redirect(){
    #ifdef LOCAL
        freopen("test.txt","r",stdin);
    #endif
}
int n;
double ans = 0;
inline int sgn(double x){
    return fabs(x)<eps?0:(x>0)?1:-1;
}
struct Point{
    double x,y;
    Point(){}
    Point(double _x,double _y){
        x = _x,y = _y;
    }
    bool operator ==(const Point &b)const{
        return (sgn(x-b.x)==0)&&(sgn(y-b.y)==0)?true:false;
    }
    bool operator <(const Point &b)const{
        return (sgn(x-b.x)==0)?(y < b.y):(x < b.x);
    }
    Point operator -(const Point &b)const{
        return Point(x-b.x,y-b.y);
    }
    double operator ^(const Point &b)const{
		return x*b.y - y*b.x;
	}
    double operator *(const Point &b)const{
        return x*b.x + y*b.y;
    }
}p[210];
struct Line{
    Point s,t;
    Line(){}
    Line(Point _s,Point _t){
        s = _s,t = _t;
    }
    Point crosspoint(Line v){
    	double a1 = (v.t-v.s)^(s-v.s);
    	double a2 = (v.t-v.s)^(t-v.s);
    	return Point((s.x*a2-t.x*a1)/(a2-a1),(s.y*a2-t.y*a1)/(a2-a1));
    }
    bool pointonseg(Point q){
	   return sgn((q-s)^(t-s)) == 0 && sgn((q-s)*(q-t)) <= 0;
    }
};
inline bool pointonpoly(Point q){
    int res = 0;
    for(int i = 0;i < n;i++){
        if(Line(p[i],p[i+1]).pointonseg(q))return true;
        int d1 = sgn(p[i].y - q.y), 
            d2 = sgn(p[i+1].y - q.y),
            k = sgn((p[i+1] - p[i])^(q - p[i]));
        if (k > 0 && d1 <= 0 && d2 > 0)res++;
        if (k < 0 && d2 <= 0 && d1 > 0)res--;
    }
    return res ? true : false;
}
inline double distance(const Point& a,const Point& b){
    return sqrt((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y));
}

inline void attempt(const int& p1,const int& p2){
    vector<Point>v;
    Line l(p[p1],p[p2]);
    for(int i = 0;i < n;i++){
        if(sgn((l.t-l.s)^(p[i]-l.s)) * sgn((l.t-l.s)^(p[i+1]-l.s)) <= 0){
            Point v1 = l.t - l.s,v2 = p[i+1] - p[i];
            if(sgn(v1^v2) == 0){
                v.push_back(p[i]);
                v.push_back(p[i+1]);
            }
            else v.push_back(l.crosspoint(Line(p[i],p[i+1])));
        }
    }
    sort(v.begin(),v.end());
    v.resize(unique(v.begin(),v.end()) - v.begin());
    int cnt = v.size();
    double res = 0;
    for(int i = 1;i < cnt;i++){
        if(pointonpoly(Point((v[i-1].x+v[i].x)/2.0,(v[i-1].y+v[i].y)/2.0)))
        res += distance(v[i-1],v[i]);
        else{
            res = 0;
            if(distance(v[i],v.back()) <= ans)return;
        }
        ans = max(ans,res);
    }
}
int main(){
    redirect();
    scanf("%d",&n);
    for(int i = 0;i < n;i++)scanf("%lf %lf",&p[i].x,&p[i].y);
    p[n].x = p[0].x,p[n].y = p[0].y;
    for(int i = 0;i < n;i++)
    for(int j = i+1;j < n;j++)
    attempt(i,j);
    printf("%.9fn",ans);
    return 0;
}

附，一组自己查错样例

10
0 0
3 4
6 0
9 4
12 0
12 10
9 6
6 10
3 6
0 10

答案为12.649110641

最后

以上就是欢呼香菇为你收集整理的2017 ACM-ICPC world final A.Airport Construction 计算几何链接：题意：思路：附：官方题解代码：的全部内容，希望文章能够帮你解决2017 ACM-ICPC world final A.Airport Construction 计算几何链接：题意：思路：附：官方题解代码：所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。