2017 ACM-ICPC World Finals A Airport Construction(计算几何)

Description:

The tropical island nation of Piconesia is famous for its beautiful beaches, lush vegetation, cocoa and coffee plantations, and wonderful weather all year round. This paradise is being considered as a future location for the World Finals of the ACM International Collegiate Programming Contest (or at the very least a vacation spot for the executive council). There is only one small problem: the island is really hard to reach.

Currently, the fastest way to reach the island takes three days from the nearest airport, and uses a combination of fishing boat, oil tanker, kayak, and submarine. To make attending the ICPC World Finals slightly easier and to jump-start the island’s tourism business, Piconesia is planning to build its first airport.

Since longer landing strips can accommodate larger airplanes, Piconesia has decided to build the longest possible landing strip on their island. Unfortunately, they have been unable to determine where this landing strip should be located. Maybe you can help?

For this problem we model the boundary of Piconesia as a polygon. Given this polygon, you need to compute the length of the longest landing strip (i.e., straight line segment) that can be built on the island. The landing strip must not intersect the sea, but it may touch or run along the boundary of the island. Figure 1 shows an example corresponding to the first sample input.

Figure 1: The island modeled as a polygon. The longest possible landing strip is shown as a thick line.

Input:

The input starts with a line containing an integer $n$n ( $3\le n\le 200$3≤n≤200) specifying the number of vertices of the polygon. This is followed by $n$n lines, each containing two integers $x$x and $y$y ( $\mid x\mid ,\mid y\mid \le 106$∣x∣,∣y∣≤106) that give the coordinates $(x,y)$(x,y) of the vertices of the polygon in counter-clockwise order. The polygon is simple, i.e., its vertices are distinct and no two edges of the polygon intersect or touch, except that consecutive edges touch at their common vertex. In addition, no two consecutive edges are collinear.

Output:

Display the length of the longest straight line segment that fits inside the polygon, with an absolute or relative error of at most $10^{-6}$10−6 .

Sample Input:

7
0 20
40 0
40 20
70 50
50 70
30 50
0 50

Sample Output:

76.157731059

Sample Input:

3
0 2017
-2017 -2017
2017 0

Sample Output:

4510.149110617

题目链接

中文题面请看

BZOJ 4948

给出⼀个 $n$n 个点的简单多边形（不一定为凸多边形），求多边形内部的最长线段长度。

显然最长线段一定在某两顶点连线所在的直线上取得，因为若不在两顶点所在直线则可以平移旋转到更优（长）的两顶点所在直线上，所以枚举两点连线即可。

在枚举两顶点所在直线时须判断此直线是否被多边形某些边切断，若切断则需要将在多边形内部的每一段取出判断是否更新线段的最大值。

做计算几何题目的时候精度问题要时刻注意。

AC代码:

#include <bits/stdc++.h>
using namespace std;

typedef long double db;
const int maxn = (int)(2e2 + 5);
const db eps = 1e-8;

int Sgn(db Key) {return fabs(Key) < eps ? 0 : (Key < 0 ? -1 : 1);}
struct Point {db X, Y;};
typedef Point Vector;
Vector operator + (Vector Key1, Vector Key2) {return (Vector){Key1.X + Key2.X, Key1.Y + Key2.Y};}
Vector operator - (Vector Key1, Vector Key2) {return (Vector){Key1.X - Key2.X, Key1.Y - Key2.Y};}
db operator * (Vector Key1, Vector Key2) {return Key1.X * Key2.X + Key1.Y * Key2.Y;};
db operator ^ (Vector Key1, Vector Key2) {return Key1.X * Key2.Y - Key1.Y * Key2.X;};
db DisPointToPoint(Point Key1, Point Key2) {return sqrt((Key2 - Key1) * (Key2 - Key1));}
struct Line {Point S, T;};
typedef Line Segment;
db DisLineToSeg(Line Key1, Segment Key2) {return ((Key2.S - Key1.S) ^ (Key2.T - Key1.S)) / ((Key2.T - Key2.S) ^ (Key1.T - Key1.S)) * DisPointToPoint(Key1.S, Key1.T);}

struct Status{db Length; int Flag;};
bool operator < (Status Key1, Status Key2) {return Sgn(Key2.Length - Key1.Length) > 0;}

int N;
Point Island[maxn];
db Ans;
Status Intersection[maxn];

void Solve(Line Key) {
    int Tot = 0;
    for (int i = 1; i <= N; ++i) {
        int Dir1 = Sgn((Key.T - Key.S) ^ (Island[i] - Key.S)), Dir2 = Sgn((Key.T - Key.S) ^ (Island[i % N + 1] - Key.S));
        if (Dir1 == Dir2) continue;
        if (Dir1 > Dir2) Intersection[++Tot] = (Status){DisLineToSeg(Key, (Segment){Island[i], Island[i % N + 1]}), (Dir1 && Dir2) ? 2 : 1};
        else Intersection[++Tot] = (Status){DisLineToSeg(Key, (Segment){Island[i], Island[i % N + 1]}), (Dir1 && Dir2) ? -2 : -1};
    }
    sort(Intersection + 1, Intersection + Tot + 1);
    int Flag = 0; db Len = 0.0;
    for (int i = 1; i <= Tot; ++i) {
        if (Flag) Len += Intersection[i].Length - Intersection[i - 1].Length;
        else {
            if (Sgn(Len - Ans) >= 0) Ans = Len;
            Len = 0.0;
        }
        Flag += Intersection[i].Flag;
    }
    if (Sgn(Len - Ans) >= 0) Ans = Len;
}

int main(int argc, char *argv[]) {
    scanf("%d", &N);
    for (int i = 1; i <= N; ++i) scanf("%Lf%Lf", &Island[i].X, &Island[i].Y);
    for (int i = 1; i <= N; ++i)
        for (int j = i + 1; j <= N; ++j)
            Solve((Segment){Island[i], Island[j]});
    printf("%.9Lf\n", Ans);
    return 0;
}