Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

各路大神求助啊,小弟代码不知道哪里有问题了,求改正啊,谢谢

Posted by yangheyu at 2012-08-25 15:53:57 on Problem 3608
测试了很多数据,都没找到问题
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator