soj2434计算几何线段相交问题.cpp

一些ACM题目的解答,主要是soj和poj的

#include<stdio.h>

#define min(a,b) (a<b?a:b)

#define max(a,b) (a>b?a:b)

int direction(int a,int b,int c,int d,int e,int f)
{
    int p1x = e-a;
    int p1y = f-b;
    int p2x = c-a;
    int p2y = d-b;
    return (p1x * p2y - p2x * p1y);
}

bool on_segment(int a,int b,int c,int d,int e,int f)
{
    if(min(a,c)<=e&&e<=max(a,c)&&min(b,d)<=f&&f<=max(b,d))
        return true;
    return false;
}

bool segment_intersect(int a,int b,int c,int d,int e,int f,int g,int h)
{
    int d1 = direction(e,f,g,h,a,b);
    int d2 = direction(e,f,g,h,c,d);
    int d3 = direction(a,b,c,d,e,f);
    int d4 = direction(a,b,c,d,g,h);

    if((d1>0&&d2<0||d1<0&&d2>0)&&(d3>0&&d4<0||d3<0&&d4>0))
        return true;
    else if(d1==0&&on_segment(e,f,g,h,a,b))
        return true;
    else if(d2==0&&on_segment(e,f,g,h,c,d))
        return true;
    else if(d3==0&&on_segment(a,b,c,d,e,f))
        return true;
    else if(d4==0&&on_segment(a,b,c,d,g,h))
        return true;
    else 
        return false;
}

int main(void)
{
    int xs,ys,xe,ye,xl,yt,xr,yb;
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int flag = 0;
        scanf("%d%d%d%d%d%d%d%d",&xs,&ys,&xe,&ye,
            &xl,&yt,&xr,&yb);
        if((xs>=xl&&xs<=xr&&ys>=yb&&ys<=yt)||(xe>=xl&&xe<=xr&&ye>=yb&&ye<=yt))
            flag=1;
        else if(segment_intersect(xs,ys,xe,ye,xl,yt,xr,yb))
            flag=1;
        else if(segment_intersect(xs,ys,xe,ye,xl,yb,xr,yt))
            flag=1;
        if(flag)
            printf("T\n");
        else
            printf("F\n");
    }
    return 0;
}