| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
各路大神求助啊,小弟代码不知道哪里有问题了,求改正啊,谢谢测试了很多数据,都没找到问题
#include<stdio.h>
#include<math.h>
#include<algorithm>
using namespace std;
struct point{double x,y,len;}p1[20005],p2[20005],st1[20005],st2[20005],A,temp;
double min(double,double);
double cross(point,point,point);
double lenth(point,point);
bool cmp(point,point);
void Graham(point*,point*,int&,int);
double L_line(point,point,point);
double dis_line(point,point,point,point);
void doing(point*,point*,int,int);
int m,n,i,tp1,tp2,nb;
double ans,k;
int main(void)
{
while(scanf("%d%d",&m,&n))
{
if(m==0&&n==0) break;
for(i=0;i<m;i++) scanf("%lf%lf",&p1[i].x,&p1[i].y);
for(i=0;i<n;i++) scanf("%lf%lf",&p2[i].x,&p2[i].y);
Graham(p1,st1,tp1,m);
Graham(p2,st2,tp2,n);
ans=L_line(p2[0],p1[0],p1[1]);
doing(st1,st2,tp1,tp2);
//doing(st2,st1,tp2,tp1);
printf("%.5lf\n",ans);
}
return 0;
}
double min(double a,double b){return a<b?a:b;}
double cross(point a,point b,point c){return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);}
double lenth(point a,point b){return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}
bool cmp(point a,point b)
{
k=cross(A,a,b);
if(k>0) return true;
if(k<0) return false;
a.len=lenth(A,a);
b.len=lenth(A,b);
return a.len>b.len;
}
void Graham(point*p,point*st,int&tp,int num)
{
A=p[0];
nb=0;
for(i=1;i<num;i++)
{
if((p[i].y<A.y||p[i].y==A.y&&p[i].x<A.x&&p==p1)||(p[i].y>A.y||p[i].y==A.y&&p[i].x>A.x&&p==p2))
{
A=p[i];
nb=i;
}
}
temp=p[0];
p[0]=p[nb];
p[nb]=temp;
A=p[0];
sort(p+1,p+num,cmp);
p[num]=p[0];
st[0]=p[0];
st[1]=p[1];
st[2]=p[2];
tp=2;
for(i=3;i<=num;i++)
{
while(cross(st[tp-1],st[tp],p[i])<=0&&tp>1) tp--;
st[++tp]=p[i];
}
}
double L_line(point a,point b,point c)
{
double line,ax,bx,cx;
ax=lenth(a,b);
bx=lenth(b,c);
cx=lenth(a,c);
line=fabs(cross(a,b,c))/bx;
if(ax*ax+bx*bx<cx*cx||bx*bx+cx*cx<ax*ax) line=min(ax,cx);
return line;
}
double dis_line(point a,point b,point c,point d)
{
double ds,bs;
ds=min(L_line(a,c,d),L_line(b,c,d));
bs=min(L_line(c,a,b),L_line(d,a,b));
return min(bs,ds);
}
void doing(point*q1,point*q2,int m,int n)
{
int q=0;
for(i=0;i<m;i++)
{
while(fabs(cross(st1[i],st1[(i+1)%m],st2[q]))>fabs(cross(st1[i],st1[(i+1)%m],st2[(q+1)%n])))
{
q=(q+1)%n;
//ans=min(ans,dis_line(st1[i],st1[(i+1)%m],st2[q],st2[(q-1)%n]));
}
ans=min(ans,dis_line(st1[i],st1[(i+1)%m],st2[q],st2[(q+1)%n]));
}
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator