호남대학 교 ACM 프로 그래 밍 신 생 컵 대회 (싱크로 나 이 즈 드 게임) C - Do you like Banana?[얼마나]

시간 제한: C / C + + 1 초, 기타 언어 2 초 공간 제한: C / C + + 32768 K, 기타 언어 65536 K 64bit IO 포맷:% lld 제목 설명
평면 상의 두 선 세그먼트 의 두 끝 점 은 두 세그먼트 가 교차 하 는 지 여 부 를 결정 하기 위해 주어 집 니 다 (공통 점 이 있 거나 교차 하 는 부분 적 인 일치 가 있 음). 교차 하 는 경우 "예" 를 출력 하고 "아니오" 를 출력 합 니 다. 입력 설명: 첫 번 째 선 은 입력 된 테스트 의 수 를 나타 내 는 T 의 수 입 니 다.(1 <= T <= 1000) For next T line,each line contains 8 numbers , x1,y1,x2,y2,x3,y3,x4, y4. (8-10 ^ < = xi, yi < = 10 ^ 8) (the two endpoints of line 1 are x1, y1, |, x2, y2, and two of the endpoints of line 2 are x3, y3, |, x4, y4)출력 설명: 각 테스트 케이스 의 경우 두 세그먼트 가 교차 하 는 경우 출력 "Yes", else 출력 "No". 예제 1 입력
2, 1, 2, 1, 0, 2, 2. - 1, 1, 1, 0, 1, 1, 출력.
Yes No
문제: 두 선분 이 교차 할 수 있 는 지 를 구하 세 요.

#include
#include
#include
#include
using namespace std;
///----------alg 1------------
struct Point
{
    double x, y;
};

bool between(double a, double X0, double X1)
{
    double temp1 = a - X0;
    double temp2 = a - X1;
    if ((temp1<1e-8 && temp2>-1e-8) || (temp2<1e-6 && temp1>-1e-8))
    {
        return true;
    }
    else
    {
        return false;
    }
}


//             ，         
// p1,p2         
// p3,p4         
bool detectIntersect(Point p1, Point p2, Point p3, Point p4)
{
    double line_x, line_y; //  
    if ((fabs(p1.x - p2.x)<1e-6) && (fabs(p3.x - p4.x)<1e-6))
    {
        return false;
    }
    else if ((fabs(p1.x - p2.x)<1e-6)) //     p1p2   y 
    {
        if (between(p1.x, p3.x, p4.x))
        {
            double k = (p4.y - p3.y) / (p4.x - p3.x);
            line_x = p1.x;
            line_y = k*(line_x - p3.x) + p3.y;

            if (between(line_y, p1.y, p2.y))
            {
                return true;
            }
            else
            {
                return false;
            }
        }
        else
        {
            return false;
        }
    }
    else if ((fabs(p3.x - p4.x)<1e-6)) //     p3p4   y 
    {
        if (between(p3.x, p1.x, p2.x))
        {
            double k = (p2.y - p1.y) / (p2.x - p1.x);
            line_x = p3.x;
            line_y = k*(line_x - p2.x) + p2.y;

            if (between(line_y, p3.y, p4.y))
            {
                return true;
            }
            else
            {
                return false;
            }
        }
        else
        {
            return false;
        }
    }
    else
    {
        double k1 = (p2.y - p1.y) / (p2.x - p1.x);
        double k2 = (p4.y - p3.y) / (p4.x - p3.x);

        if (fabs(k1 - k2)<1e-6)
        {
            return false;
        }
        else
        {
            line_x = ((p3.y - p1.y) - (k2*p3.x - k1*p1.x)) / (k1 - k2);
            line_y = k1*(line_x - p1.x) + p1.y;
        }

        if (between(line_x, p1.x, p2.x) && between(line_x, p3.x, p4.x))
        {
            return true;
        }
        else
        {
            return false;
        }
    }
}
///------------alg 1------------

int main()
{
    int T;
    scanf("%d", &T);
    while (T--) {
        double x1, x2, x3, x4;
        double y1, y2, y3, y4;
        scanf("%lf%lf%lf%lf%lf%lf%lf%lf", &x1, &y1, &x2, &y2, &x3, &y3, &x4, &y4);
        Point p1, p2, p3, p4;
        p1.x = x1, p1.y = y1;
        p2.x = x2, p2.y = y2;
        p3.x = x3, p3.y = y3;
        p4.x = x4, p4.y = y4;
        if (detectIntersect(p1, p2, p3, p4)) {
            printf("Yes
");
        }
        else
        {
            printf("No
");
        }
    }
    return 0;
}