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 hzauxiaoze at 2014-08-05 22:17:37 on Problem 1410
struct point  //定义点
{
    double x;
    double y;
};

typedef point vector;  //引申为向量

vector operator -(vector a,vector b) //向量减法
{
    point v;
    v.x=a.x-b.x;
    v.y=a.y-b.y;
    return v;
}

bool zero(double x)
{
    return fabs(x)<eps?true:false;
}

double fork_mul(vector a,vector b) //向量叉积
{
    return (a.x*b.y-a.y*b.x);
}

double min(double x,double y)
{
    return x<y?x:y;
}

double max(double x,double y)
{
    return x>y?x:y;
}

int intersect_sign(point a,point b,point c,point d,point &result) //两线段位置关系的标志
{
    double cba=fork_mul(b-c,a-c),dba=fork_mul(b-d,a-d),v12=fork_mul(b-a,d-c);
    if(zero(v12)==true) //两线段方向相同
    {
        if(zero(cba)==true&&zero(dba)==true) //两线段共线
        {
            if(min(a.x,b.x)<max(c.x,d.x)&&min(c.x,d.x)<max(a.x,b.x)&&min(a.y,b.y)<max(c.y,d.y)&&min(c.y,d.y)<max(a.y,b.y))
                return -3; //重叠共线
            if(min(a.x,b.x)>max(c.x,d.x)||min(c.x,d.x)>max(a.x,b.x)||min(a.y,b.y)>max(c.y,d.y)||min(c.y,d.y)>max(a.y,b.y))
                return -2; //分离共线
            return -1; //首尾相接
        }
        else
            return 0; //两线段平行
    }
    else //两线段方向不同,它们各自所在的直线相交
    {
        double bdc=fork_mul(d-b,c-b),adc=fork_mul(d-a,c-a);
        result.x=(dba*c.x-cba*d.x)/(dba-cba); //求两线段所在直线的交点
        result.y=(dba*c.y-cba*d.y)/(dba-cba);
        if(dba*cba<=0&&bdc*adc<=0)
            return 1; //线段相交
        else
            return 2; //线段不相交
    }
}


注:若只判断线段是否相交,将标志对2取余即可,0为不相交,非0为相交

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