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