题面
http://codeforces.com/gym/101471/attachments A题
题解
前置知识
肉眼目测答案线段至少通过两个多边形顶点。
枚举这两个顶点，判线段是否在多边形内。
若是，将其两边延长直到碰到多边形的边，然后用延长后的边更新答案。
代码
#include<bits/stdc++.h>
using namespace std;
#define rg register
#define In inline
#define ld long double
const ld eps = 1e-7;
const int N = 200;
In int read(){
int s = 0,ww = 1;
char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-')ww = -1;ch = getchar();}
while('0' <= ch && ch <= '9'){s = 10 * s + ch - '0';ch = getchar();}
return s * ww;
}
In int sgn(ld x){return x < -eps ? -1 : x > eps;}
In ld sqr(ld x){return x * x;}
struct vec{
ld x,y;
vec(){}
vec(ld _x,ld _y){x = _x,y = _y;}
In friend vec operator + (vec a,vec b){
return vec(a.x + b.x,a.y + b.y);
}
In friend vec operator - (vec a,vec b){
return vec(a.x - b.x,a.y - b.y);
}
In friend vec operator * (vec a,ld k){
return vec(a.x * k,a.y * k);
}
In friend vec operator / (vec a,ld k){
return vec(a.x / k,a.y / k);
}
In friend ld Dot(vec a,vec b){
return a.x * b.x + a.y * b.y;
}
In friend ld Cross(vec a,vec b){
return a.x * b.y - a.y * b.x;
}
In friend bool InUpper(vec a){
return sgn(a.y) > 0 || (sgn(a.y) == 0 && sgn(a.x) > 0);
}
In friend bool prl(vec a,vec b){
return sgn(Cross(a,b)) == 0;
}
In friend bool samedir(vec a,vec b){
return prl(a,b) && sgn(Dot(a,b)) >= 0;
}
In friend ld len(vec a){
return sqrt(sqr(a.x) + sqr(a.y));
}
};
struct seg{
vec p,q;
seg(){}
seg(vec _p,vec _q){p = _p,q = _q;}
In friend bool prl(seg a,seg b){
return prl(a.q - a.p,b.q - b.p);
}
In friend bool samedir(seg a,seg b){
return samedir(a.q - a.p,b.q - b.p);
}
In friend bool OnSeg(seg a,vec p){
return samedir(p - a.p,a.q - a.p) && samedir(p - a.q,a.p - a.q);
}
In friend vec Its(seg a,seg b){
ld x = Cross(b.q - b.p,a.p - b.p);
ld y = Cross(a.q - a.p,b.q - b.p);
return a.p + (a.q - a.p) * x / y;
}
};
vec p[N+5];
seg a[N+5],t[N+5];
int n;
ld ans;
In bool cmp(seg a,seg b){
int k = sgn(Cross(a.q-a.p,b.q-b.p));
if(k != 0)return k > 0;
return len(a.q - a.p) < len(b.q - b.p);
}
bool inside(vec p,seg a[],int n){ //2:in,1:on,0:out
bool rt = 0;
for(rg int i = 1;i <= n;i++){
seg s = a[i];
if(OnSeg(s,p))return 1;
if(sgn(s.p.y-s.q.y) < 0)swap(s.p,s.q);
if(sgn(p.y-s.p.y) >= 0 || sgn(p.y-s.q.y) < 0)continue;
rt ^= (sgn(Cross(s.p-p,s.q-p)) > 0);
}
return rt << 1;
}
vec P[N+5];
int Pn;
In bool cmp2(vec a,vec b){
return a.x == b.x ? a.y < b.y : a.x < b.x;
}
void check(seg s,seg a[],int n){
Pn = 0;
for(rg int i = 1;i <= n;i++){
if(prl(s,a[i]))continue;
vec p = Its(s,a[i]);
if(OnSeg(a[i],p))P[++Pn] = p;
}
if(Pn)sort(P + 1,P + Pn + 1,cmp2);
int l = 1,r = 0;
while(l < Pn && !OnSeg(s,P[l]))l++;
r = l;
while(r < Pn && OnSeg(s,P[r+1]))r++;
for(rg int i = l;i < r;i++)
if(!inside((P[i]+P[i+1])/2,a,n))return;
while(l > 1 && inside((P[l-1]+P[l])/2,a,n))l--;
while(r < Pn && inside((P[r+1]+P[r])/2,a,n))r++;
ans = max(ans,len(P[r]-P[l]));
}
int main(){
n = read();
for(rg int i = 1;i <= n;i++){
int x = read(),y = read();
p[i] = vec(x,y);
}
for(rg int i = 1;i < n;i++)a[i] = seg(p[i],p[i+1]);
a[n] = seg(p[n],p[1]);
for(rg int i = 1;i <= n;i++){
int cur = 0;
for(rg int j = 1;j <= n;j++){
if(i == j || InUpper(p[j]-p[i]))continue;
t[++cur] = seg(p[i],p[j]);
}
sort(t + 1,t + cur + 1,cmp);
for(rg int j = 1;j <= cur;j++){
if(j > 1 && samedir(t[j-1],t[j]))continue;
check(t[j],a,n);
}
}
printf("%.9lf
",(double)ans);
return 0;
}