学步园

题意：给出两个多边形（二维坐标），保证第一个在第二个的内部，这样两个多边形就可以组成一个环，求一个圆，能在该环内饶一周，且要求该圆的半径尽量大，输出这个半径值。

思路很明显，求点到线段的距离。

开始的时候一直ＷＡ，不管怎么改，方法也换了不少，就是不对。后来还是 XH 在别人的blog上发现，我们少考虑了一种情况……

就是这个了，当时想当然的只算了内环上的点到外环线段的距离，没考虑到还需要算外环上的点到内环的距离……

代码：（求距离我是用的找垂足的方法，其实可以用向量乘来求，貌似更好）

#include<stdio.h><br /> #include<string.h><br /> #include<math.h><br /> #define N 110<br /> #define aesp 0.000000001<br /> double min(double a,double b)<br /> {<br /> if(a<b)return a;<br /> else return b;<br /> }<br /> double max(double a,double b)<br /> {<br /> if(a>b)return a;<br /> else return b;<br /> }<br /> struct point<br /> {<br /> double x,y;<br /> };<br /> point p[N],lp[N];<br /> double dis(point a,point b)<br /> {<br /> return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));<br /> }<br /> int judge(point p1,point p2,point s) //s点是否在线段p1,p2上<br /> {<br /> if((min(p1.x,p2.x)<s.x || fabs(min(p1.x,p2.x)-s.x)<aesp) && ( s.x<max(p1.x,p2.x) || fabs(max(p1.x,p2.x)-s.x)<aesp) &&<br /> (min(p1.y,p2.y)<s.y || fabs(min(p1.y,p2.y)-s.y)<aesp) && ( s.y<max(p1.y,p2.y) || fabs(max(p1.y,p2.y)-s.y)<aesp) )<br /> return 1;<br /> return 0;<br /> }<br /> double mindis(point p1,point p2,point q)<br /> {<br /> int flag=1;<br /> double k;<br /> point s;<br /> if(p1.x==p2.x)<br /> s.x=p1.x, s.y=q.y, flag=0;<br /> if(p1.y==p2.y)<br /> s.x=q.x, s.y=p1.y, flag=0;<br /> if(flag)<br /> {<br /> k=(p2.y-p1.y)/(p2.x-p1.x);<br /> s.x=(k*k*p1.x+k*(q.y-p1.y)+q.x)/(k*k+1);<br /> s.y=k*(s.x-p1.x)+p1.y;<br /> }<br /> if(judge(p1,p2,s))<br /> return dis(q,s);<br /> else return min(dis(q,p1),dis(q,p2));<br /> }<br /> int main()<br /> {<br /> int i,j,t1,t2,t;<br /> scanf("%d",&t);<br /> while(t--)<br /> {<br /> memset(p,0,sizeof(p));<br /> memset(lp,0,sizeof(lp));<br /> scanf("%d",&t1);<br /> for(i=1;i<=t1;i++)<br /> scanf("%lf%lf",&p[i].x,&p[i].y);<br /> scanf("%d",&t2);<br /> for(i=1;i<=t2;i++)<br /> scanf("%lf%lf",&lp[i].x,&lp[i].y);<br /> double m=999999999.0;<br /> for(i=1;i<=t1;i++) //内环上的点到外环线段的距离<br /> {<br /> double y=mindis(lp[1],lp[t2],p[i]);<br /> if(y<m)m=y;<br /> for(j=1;j<t2;j++)<br /> {<br /> double x=mindis(lp[j],lp[j+1],p[i]);<br /> if(x<m)m=x;<br /> }<br /> }<br /> for(i=1;i<=t2;i++) //外环上的点到内环线段的距离<br /> {<br /> double y=mindis(p[1],p[t1],lp[i]);<br /> if(y<m)m=y;<br /> for(j=1;j<t1;j++)<br /> {<br /> double x=mindis(p[j],p[j+1],lp[i]);<br /> if(x<m)m=x;<br /> }<br /> }<br /> printf("%.8lf/n",m/2);<br /> }<br /> return 0;<br /> }<br />