[C] 백준 - 17387번: 선분 교차 2

7월 27일(목) - 기하학 (17387번)

17387번: 선분 교차 2

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

최초 생각 정리

- 이전에 풀이했던 "17386번: 선분 교차 1" 문제와 비슷한 풀이를 예상

- 다만 3개의 점이 하나의 직선상에 위치하며 교차하는 경우를 조건에 추가해야한다 

[C] 백준 - 17386번: 선분 교차 1

 

- 3개의 점이 하나의 직선상에 위치하는 경우는 

1) 점 a가 선분 cd의 안에 위치하는 경우 -> 선분 ab와 선분 cd가 교차한다

2) 점 a가 선분 cd의 끝, 결국 점 c 혹은 점 d와 겹치는 경우 -> 선분 ab와 선분 cd가 교차한다

3) 점 a가 선분 cd의 연장선상에 위치하는 경우 -> 선분 ab와 선분 cd가 교차하지 않는다

이렇게 나누어서 생각할 수 있다

- 하지만, 4개의 점이 하나의 직선상에 위치하는 경우를 빼먹고 풀이를 시작해서 꼬이기 시작

-> 놓친 조건을 찾아보다가 아래의 풀이를 참고하게됨

백준 No.17387 [선분 교차 2]

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

문제점

// 17386번: 선분 교차 1
int cross_or_not(point a, point b, point c, point d)
{
    int first = ccw(a, b, c) * ccw(a, b, d);
    int second = ccw(c, d, a) * ccw(c, d, b);

    if (first <= 0 && second <= 0)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}


// 17387번: 선분 교차 2
int cross_or_not(point a, point b, point c, point d)
{
    int first = ccw(a, b, c) * ccw(a, b, d);
    int second = ccw(c, d, a) * ccw(c, d, b);
    
    // 추가조건 start
    if (first == 0 && second == 0)
    {
        if (oneline_or_not(a, b, c) && oneline_or_not(a, b, d) || oneline_or_not(b, a, c) && oneline_or_not(b, a, d))
        {
            return 0;
        }
        else
        {
            return 1;
        }
    }
    // 추가조건 end
    else if (first <= 0 && second <= 0)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}

1. "17386번: 선분 교차 1"의 풀이에서는 first<=0 && second<=0이라면 1을 return 하는 조건만 있었다

-> first<=0 && second<=0 는 if조건으로, 추가조건은 else if에 작성하는 과정에서 예제 7번만이 출력오류가 발생

-> 위의 풀이처럼 if와 else if의 순서를 수정해주면서 해결

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

풀이 - 1

(풀이참고 -> https://johoonday.tistory.com/107 )

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)

#include <stdio.h>

typedef struct {
    double x;
    double y;
}point;

int ccw(point first, point second, point third)
{
    double temp = (first.x * second.y) + (second.x * third.y) + (third.x * first.y);
    temp = temp - (first.y * second.x) - (second.y * third.x) - (third.y * first.x);

    if (temp > 0)
    {
        return 1;
    }
    else if (temp < 0)
    {
        return -1;
    }
    else
    {
        return 0;
    }
}

double oneline_or_not(point first, point second, point third)
{
    if (first.x < second.x)
    {
        if (second.x < third.x)
        {
            return 1;
        }
        else
        {
            return 0;
        }
    }

    else if (first.x > second.x)
    {
        if (third.x < second.x)
        {
            return 1;
        }
        else
        {
            return 0;
        }
    }

    else
    {
        if (first.y < second.y)
        {
            if (second.y < third.y)
            {
                return 1;
            }
            else
            {
                return 0;
            }
        }

        else if (first.y > second.y)
        {
            if (third.y < second.y)
            {
                return 1;
            }
            else
            {
                return 0;
            }
        }

    }
}

int cross_or_not(point a, point b, point c, point d)
{
    int first = ccw(a, b, c) * ccw(a, b, d);
    int second = ccw(c, d, a) * ccw(c, d, b);

    // 추가조건 start
    if (first == 0 && second == 0)
    {
        if (oneline_or_not(a, b, c) && oneline_or_not(a, b, d) || oneline_or_not(b, a, c) && oneline_or_not(b, a, d))
        {
            return 0;
        }
        else
        {
            return 1;
        }
    }
    // 추가조건 end
    else if (first <= 0 && second <= 0)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}

int main(void)
{
    point a, b, c, d;
    scanf("%lf %lf %lf %lf", &a.x, &a.y, &b.x, &b.y);
    scanf("%lf %lf %lf %lf", &c.x, &c.y, &d.x, &d.y);

    printf("%d", cross_or_not(a, b, c, d));

    return 0;
}

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

풀이 - 2

(swap 사용 풀이 -> https://www.acmicpc.net/source/62956714 )

#include <stdio.h>

typedef struct{
    long long x, y;
}Pair;

void swap(Pair *p, int a, int b){
    Pair temp = p[a];
    p[a] = p[b];
    p[b] = temp;
}

int ccw(Pair p1, Pair p2, Pair p3){
    long long cp = p1.x * p2.y + p2.x * p3.y + p3.x * p1.y;
    cp -= p1.y * p2.x + p2.y * p3.x + p3.y * p1.x;
    if(cp < 0)
        return 1;
    if(cp > 0)
        return -1;
    return 0;
}

int main(){
    Pair p[4];
    int i, abc, abd, cda, cdb;
    for(i = 0; i < 4; i++)
        scanf("%lld %lld", &p[i].x, &p[i].y);
    abc = ccw(p[0], p[1], p[2]);
    abd = ccw(p[0], p[1], p[3]);
    cda = ccw(p[2], p[3], p[0]);
    cdb = ccw(p[2], p[3], p[1]);
    if(abc * abd == 0 && cda * cdb == 0){
        if(p[0].x == p[1].x){
            if(p[0].y > p[1].y)
                swap(p, 0, 1);
            if(p[2].y > p[3].y)
                swap(p, 2, 3);
            if(p[0].y <= p[3].y && p[2].y <= p[1].y)
                puts("1");
            else
                puts("0");
        }
        else{
            if(p[0].x > p[1].x)
                swap(p, 0, 1);
            if(p[2].x > p[3].x)
                swap(p, 2, 3);
            if(p[0].x <= p[3].x && p[2].x <= p[1].x)
                puts("1");
            else
                puts("0");
        }        
    }
    else if(abc * abd <= 0 && cda * cdb <= 0)
        puts("1");
    else
        puts("0");

    return 0;
}

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ