【POJ 3525】Most Distant Point from the Sea(直线平移、半平面交)

时间:2022-10-21 03:39:12

按逆时针顺序给出n个点,求它们组成的多边形的最大内切圆半径。

二分这个半径,将所有直线向多边形中心平移r距离,如果半平面交不存在那么r大了,否则r小了。

平移直线就是对于向量ab,因为是逆时针的,向中心平移就是向向量左手边平移,求出长度为r方向指向向量左手边的向量p,a+p指向b+p就是平移后的向量。

半平面交就是对于每个半平面ax+by+c>0,将当前数组里的点(一开始是所有点)带入,如果满足条件,那么保留该点,否则,先看i-1号点是否满足条件,如果满足,那么将i-1和i点所在直线和直线ax+by+c=0的交点加入数组,再看i+1号点如果满足条件,那么将i和i+1号点所在直线和直线ax+by+c=0的交点加入数组。最后看数组里有多少个点,如果0个点那么就是不存在半平面交。

要注意一下向量方向,半平面的直线的方向。

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
#define dd double
#define eps 1e-5
#define N 505
using namespace std;
int n;
struct Point{
dd x,y;
}p[N],tp[N],q[N];
dd osXoe(const Point &po,const Point &ps,const Point &pe){
return (ps.x-po.y)*(pe.y-po.y)-(pe.x-po.x)*(ps.y-po.y);
}
void eq(const Point &p1,const Point &p2,dd &a,dd &b,dd &c){
a=p2.y-p1.y;
b=p1.x-p2.x;
c=p2.x*p1.y-p1.x*p2.y;
}
Point cross(Point p1,Point p2,dd a,dd b,dd c){
dd u=fabs(a*p1.x+b*p1.y+c);
dd v=fabs(a*p2.x+b*p2.y+c);
Point t;
t.x=(p1.x*v+p2.x*u)/(u+v);
t.y=(p1.y*v+p2.y*u)/(u+v);
return t;
}
int Cut(dd a,dd b,dd c,int cnt){
int tmp=;
for (int i=;i<=cnt;i++){
if(a*p[i].x+b*p[i].y+c>-eps)tp[++tmp]=p[i];
else{
if(a*p[i-].x+b*p[i-].y+c>eps)
tp[++tmp]=cross(p[i-],p[i],a,b,c);
if(a*p[i+].x+b*p[i+].y+c>eps)
tp[++tmp]=cross(p[i],p[i+],a,b,c);
}
}
for (int i=;i<=tmp;i++)p[i]=tp[i];
p[]=p[tmp];p[tmp+]=p[];
return tmp;
}
int solve(dd r){
q[]=q[n];q[n+]=q[];
for (int i=;i<=n+;i++) p[i]=q[i];
int cnt=n;
for (int i=;i<=n;i++){
dd a,b,c;
Point p1,p2,p3;
p1.y=q[i+].x-q[i].x;p1.x=q[i].y-q[i+].y;
dd k=r/sqrt(p1.x*p1.x+p1.y*p1.y);
p1.x=k*p1.x;p1.y=k*p1.y;
//p1是垂直q[i+1]->q[i]指向右手边的长度为r的向量。如果是q[i]->q[i+1]则求指向左手边的。
p2.x=p1.x+q[i].x;p2.y=p1.y+q[i].y;
p3.x=p1.x+q[i+].x;p3.y=p1.y+q[i+].y;
eq(p3,p2,a,b,c);//过p3->p2的直线方程ax+by+c=0
cnt=Cut(a,b,c,cnt);//求半平面交剩下的点
}
return cnt;
}
int main(){
while(cin>>n,n){
for (int i=;i<=n;i++)
scanf("%lf%lf",&q[i].x,&q[i].y);
dd l=,r=<<,m;
while(fabs(r-l)>eps){
m=(l+r)/2.0;
if(solve(m))l=m;
else r=m;
}
printf("%.6f\n",m);
}
}