首页 > 代码库 > You can Solve a Geometry Problem too （hdu1086）几何，判断两线段相交

You can Solve a Geometry Problem too （hdu1086）几何，判断两线段相交

2024-07-03 06:36:15   224人阅读

You can Solve a Geometry Problem too

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 6837 Accepted Submission(s): 3303


Problem Description
Many geometry（几何）problems were designed in the ACM/ICPC. And now, I also prepare a geometry problem for this final exam. According to the experience of many ACMers, geometry problems are always much trouble, but this problem is very easy, after all we are now attending an exam, not a contest :)
Give you N (1<=N<=100) segments（线段）, please output the number of all intersections（交点）. You should count repeatedly if M (M>2) segments intersect at the same point.

Note:
You can assume that two segments would not intersect at more than one point.
 
Input
Input contains multiple test cases. Each test case contains a integer N (1=N<=100) in a line first, and then N lines follow. Each line describes one segment with four float values x1, y1, x2, y2 which are coordinates of the segment’s ending.
A test case starting with 0 terminates the input and this test case is not to be processed.
 
Output
For each case, print the number of intersections, and one line one case.
 
Sample Input
2
0.00 0.00 1.00 1.00
0.00 1.00 1.00 0.00
3
0.00 0.00 1.00 1.00
0.00 1.00 1.00 0.00
0.00 0.00 1.00 0.00
0
 
Sample Output
1
3
 
ps：http://acm.hdu.edu.cn/showproblem.php?pid=1086
 
hdu 1086 判断两线段是否相交 （线段和直接是否相交）

若是判断直线和线段是否有交点，把on_segment去掉就可以了

　　判断两线段是否相交：

　　我们分两步确定两条线段是否相交：

　　(1)快速排斥试验

　　　　设以线段 P1P2 为对角线的矩形为R， 设以线段 Q1Q2 为对角线的矩形为T，如果R和T不相交，显然两线段不会相交。

　　(2)跨立试验

　　　　如果两线段相交，则两线段必然相互跨立对方。若P1P2跨立Q1Q2 ，则矢量 ( P1 - Q1 ) 和( P2 - Q1 )位于矢量( Q2 - Q1 ) 的两侧，即( P1 - Q1 ) × ( Q2 - Q1 ) * ( P2 - Q1 ) × ( Q2 - Q1 ) < 0。上式可改写成( P1 - Q1 ) × ( Q2 - Q1 ) * ( Q2 - Q1 ) × ( P2 - Q1 ) > 0。当 ( P1 - Q1 ) × ( Q2 - Q1 ) = 0 时，说明 ( P1 - Q1 ) 和 ( Q2 - Q1 )共线，但是因为已经通过快速排斥试验，所以 P1 一定在线段 Q1Q2上；同理，( Q2 - Q1 ) ×(P2 - Q1 ) = 0 说明 P2 一定在线段 Q1Q2上。所以判断P1P2跨立Q1Q2的依据是：( P1 - Q1 ) × ( Q2 - Q1 ) * ( Q2 - Q1 ) × ( P2 - Q1 ) >= 0。同理判断Q1Q2跨立P1P2的依据是：( Q1 - P1 ) × ( P2 - P1 ) * ( P2 - P1 ) × ( Q2 - P1 ) >= 0。具体情况如下图所示：

    

　　在相同的原理下，对此算法的具体的实现细节可能会与此有所不同，除了这种过程外，大家也可以参考《算法导论》上的实现。

关于计算几何算法概述网站 http://dev.gameres.com/Program/Abstract/Geometry.htm 一个挺好的网站

 

 

#include<stdio.h>//判断线段相交模版

struct point
{
    double x,y;
};

double direction( point p1,point p2,point p )
{
    //叉乘符号，向量a(x1,y1)×向量b(x2,y2)=x1*y2-x2*y1;
    return ( p1.x -p.x )*( p2.y-p.y) -  ( p2.x -p.x )*( p1.y-p.y)  ;
}

int on_segment( point p1,point p2 ,point p )
{
    double max=p1.x > p2.x ? p1.x : p2.x ;
    double min =p1.x < p2.x ? p1.x : p2.x ;

    if( p.x >=min && p.x <=max )
        return 1;
    else
        return 0;
}

int segments_intersert( point p1,point p2,point p3,point p4 )
{
    double d1,d2,d3,d4;
    //判断p3和p4是否在p1和p2两侧
    d1 = direction ( p1,p2,p3 );
    d2 = direction ( p1,p2,p4 );
    //判断p1和p2是否在p3和p4两侧
    d3 = direction ( p3,p4,p1 );
    d4 = direction ( p3,p4,p2 );
    if( d1*d2<0 && d3*d4<0 )//在两侧，说明p1p2和p3p4相交
        return 1;
    else if( d1==0 && on_segment( p1,p2,p3 ) )
        return 1;
    else if( d2==0 && on_segment( p1,p2,p4 ) )
        return 1;
    else if( d3==0 && on_segment( p3,p4,p1 ) )
        return 1;
    else if( d4==0 && on_segment( p3,p4,p2 ) )
        return 1;

    return 0;
}

int main()
{
    int n,i,j,num;
    point begin[105],end[105];  //结构体数组

    while(scanf("%d",&n)&&n!=0 )
    {
        num=0;
        for(i=0;i<n;i++)
        {
            scanf("%lf%lf%lf%lf",&begin[i].x ,&begin[i].y ,&end[i].x ,&end[i].y );
        }
        for(i=0;i<n;i++)//线段两两比较
        {
            for(j=i+1;j<n;j++)
            {
                if( segments_intersert( begin[i],end[i],begin[j],end[j] ) )
                    num++;
            }
        }
        printf("%d\n",num);
    }
    return 0;
}

 

 

几何，哥哥要征服你，fighting！


联系
我们