自动搬运

查看原文

来自洛谷，原作者为

	constexpr Stop learning useless algorithms, go and solve some problems, learn how to use binary search.

搬运于2025-08-24 22:25:15，当前版本为作者最后更新于2022-07-06 08:51:10，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

首先观察多边形内最长线段的性质：

可以发现最长的线段至少经过多边形上的两点。考虑枚举两点。

但是线段的端点未必是枚举的两个点，并且不能保证线段完全在多边形内部。

先考虑线段端点的问题。可以以这两点间的线段为基础，向线段的两端扩展。

由于线段需要在多边形的内部，考虑求出这条线段所在直线与这个多边形的所有交点，并找出所有两端中至少一端为多边形外部的点，找到不在线段上离线段最近的两点即可。注意线段两端点也需要判断。

接下来需要验证线段是否完全在多边形内部。首先在扩展线段时向外延伸的部分是一定在多边形内部的。而判断线段原本的部分只需要判断这一部分存不存在两端中至少一端为多边形外部的点即可。

但是注意有一种特殊情况，如下图所示：

这种情况下，线段原本的部分没有多边形任何部分相交。

对于这一种情况，使用多边形的面积可以较为方便地判断。

具体来说，预处理出整个多边形的面积 $S$，设两点分别为 $i,j$，则计算出由点 $i$ 到点 $j$ 构成多边形的面积 $S_1$ 以及剩下的点和 $i,j$ 构成多边形的面积 $S_2$，判断 $S_1+S_2$ 是否等于 $S$ 即可。若相等，则线段在多边形内部。

接下来是一些代码细节上的处理问题：

求解直线与多边形交点时，需要特判直线与多边形的边平行的情况。

除此以外，交点可能恰好在多边形的点上，这种情况下需要分以下两种情况讨论。

• 该点所在内角 $< 180\degree$，这种情况下直线一定会有一端在多边形外。
• 该点所在内角 $\geq 180\degree$，这种情况下需要判断直线与角的位置关系。

对于上述第二种情况，观察下面两张图：

令端点为 $A$，与端点相邻的两个点为 $B,C$，直线的方向向量为 $\textbf{v}$，则直线穿过多边形边界的充要条件为 $\operatorname{sgn}(\overrightarrow{AB} \times \textbf{v}) \cdot \operatorname{sgn}(\textbf{v} \times \overrightarrow{AC}) \geq 0$。

枚举两端点需要 $O(n^2)$，对于每一条线段，需要 $O(n \log n)$ 的时间去处理，复杂度瓶颈在于对与多边形相交所有点的排序。总时间复杂度 $O(n^3 \log n)$。

代码：

#include <cstdio>
#include <ctime>
#include <cmath>
#include <cstdlib>
#include <vector>
#define double long double
const int N=210;
const double inf=1e9,pi=acos(-1),eps=1e-7;
int n;
double ans,farea,l[N],r[N];
bool vis[N];
namespace basic{
	int res;char cdc;bool ng;
	template<typename T>T sq(T x){return x*x;}
	template<typename T>T rv(T x){return x>T()?x:(-x);}
	template<typename T>void cmin(T &x,T y){if(x>y)x=y;}
	template<typename T>void cmax(T &x,T y){if(x<y)x=y;}
	template<typename T>void swp(T &x,T &y){T z=x;x=y;y=z;}
	inline int read(){
		res=0,ng=false;
		for(;cdc<'0'||cdc>'9';cdc=getchar())ng|=cdc=='-';
		for(;!(cdc<'0'||cdc>'9');cdc=getchar())res=(res<<1)+(res<<3)+(cdc^48);
		return ng?~res+1:res;
	}
}using basic::sq;using basic::rv;using basic::cmin;using basic::cmax;using basic::swp;using basic::read;
struct cpx{
	double x,y;
	cpx():x(0),y(0){};
	cpx(double x,double y):x(x),y(y){};
	inline cpx operator-()const{return cpx(-x,-y);}
	inline cpx operator+(const cpx &nxt)const{return cpx(x+nxt.x,y+nxt.y);}
	inline cpx operator-(const cpx &nxt)const{return cpx(x-nxt.x,y-nxt.y);}
	inline cpx operator*(double w)const{return cpx(x*w,y*w);}
	inline cpx operator/(double w)const{return cpx(x/w,y/w);}
	inline double operator|(const cpx &nxt)const{return x*nxt.x+y*nxt.y;}
	inline double operator&(const cpx &nxt)const{return x*nxt.y-y*nxt.x;}
	inline bool operator<(const cpx &nxt)const{return x<nxt.x||(x==nxt.x&&y<nxt.y);}
	inline bool operator>(const cpx &nxt)const{return x>nxt.x||(x==nxt.x&&y>nxt.y);}
	inline double len()const{return sqrt(sq(x)+sq(y));}
	inline cpx bk()const{return *this/len();}
}crr[N];std::vector<cpx> vec;
struct line{
	cpx u,v;
	line(){};
	line(const cpx &u,const cpx &v):u(u),v(v){};
}lrr[N];
inline double area(const cpx &a,const cpx &b,const cpx &c){return ((b-a)&(c-a))/2;}
inline bool ponline(const cpx &a,const line &b){return rv((b.u-a)&(b.v-a))<eps;}
inline bool online(const cpx &a,const line &b){return ponline(a,b)&&((b.u-a)|(b.v-a))<-eps;}
inline double dist(const cpx &a,const line &b){return rv(area(a,b.u,b.v))*2/(b.u-b.v).len();}
inline cpx depart(const cpx &a,const cpx &b,double da,double db){return (a*db+b*da)/(da+db);}
inline cpx inter(const line &a,const line &b){return depart(a.u,a.v,area(a.u,b.u,b.v),area(a.v,b.v,b.u));}
double f(int i,int j){
	std::vector<cpx> vec;
	while(i!=j)vec.push_back(crr[i]),i=i==n?1:i+1;
	vec.push_back(crr[j]);int len=vec.size();double res=0;
	for(int p=0;p<len;++p)res+=(vec[p]&vec[(p+1)%len])/2;
	return rv(res);
}
void check(line c){
	vec.clear();cpx p,mn=cpx(-inf,-inf),mx=cpx(inf,inf);
	if(c.u>c.v)swp(c.u,c.v);
	for(int i=1;i<=n;++i){
		p=inter(c,lrr[i]);
		if(!online(p,lrr[i])||rv((lrr[i].v-lrr[i].u)&(c.v-c.u))<eps)continue;
		vec.push_back(p);
	}
	for(int i=1;i<=n;++i){
		if(!ponline(crr[i],c))continue;
		cpx a=crr[i==1?n:i-1],b=crr[i==n?1:i+1],t=crr[i];
		if(vis[i]||((a-t)&(c.u-c.v))*((c.u-c.v)&(b-t))>eps)vec.push_back(crr[i]);
	}
	for(cpx i:vec){
		if(!(i>c.u))cmax(mn,i);
		if(!(i<c.v))cmin(mx,i);
		if(i>c.u&&i<c.v)return;
	}
	cmax(ans,(mx-mn).len());
}
int main(){
	srand(time(NULL)),n=read();
	for(int x,y,i=1;i<=n;++i){
		x=read(),y=read();
		crr[i]=cpx(x,y);
	}
	farea=f(1,n);
	for(int i=1;i<=n;++i)lrr[i]=line(crr[i],crr[i==n?1:i+1]),vis[i]=((crr[i]-crr[i==1?n:i-1])&(crr[i==n?1:i+1]-crr[i]))>eps;
	for(int i=1;i<=n;++i){
		for(int j=i+1;j<=n;++j){
			if(j!=i+1&&rv(f(i,j)+f(j,i)-farea)>eps)continue;
			check(line(crr[i],crr[j]));
		}
	}
	printf("%.9Lf",ans);
	return 0;
}