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

7월 20일(목) - 기하학 (17386번)

17386번: 선분 교차 1

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

 

최초 생각 정리

- 선분 교차여부를 무엇으로 판단해야할지 감이 잡히지 않아서 검색한 결과, CCW 알고리즘의 활용을 알게됨

- CCW 알고리즘을 이미 사용한 적이 있지만 그 의미를 정확히 모르고 사용했었기에, 이에 대한 공부부터 시작

 

- 3개의 점의 방향성을 시계방향 / 반시계방향 / 일직선 3가지로 나눌 수 있다는 점을 활용해야한다

- 이를 통해서 ccw 계산을 총 4번을 해야한다

  점 c와 점 d가 점 a,b로 이루어진 선분 ab에 대해서 각각 반대 방향에 위치하는 지를 계산하고

  점 a와 점 b가 점 c,d로 이루어진 선분 cd에 대해서 각각 반대 방향에 위치하는 지를 계산한다

- 반대 방향에 위치하는지는 ccw값의 곱이 0보다 작거나 같다는 조건을 활용한다

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

 

문제점

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;
    }
}

1. ccw 알고리즘과 관련해서 이전에 "11758번: CCW" 문제를 깊게 풀이하지 않았었다

-> 단순히 외적 관련 식의 변형이라고만 생각했던 점을 수정하고, 해당 알고리즘에 대해서 더 알아봄

점 3개의 방향성을 나타내는 CCW

[알고리즘] 세 점의 방향성 파악하기 'CCW 알고리즘'

 

2. 알고리즘 전반적인 내용이 아니라, 이번 17386번 풀이과정 중에서는 변수 temp의 자료형에 대한 문제가 발생

-> 입력받는 x,y좌표의 범위를 고려하여 double 자료형으로 입력받았지만,

     기존 ccw알고리즘의 내용을 그래도 활용하며 변수 temp는 int 자료형으로 사용했고,

-> 틀렸습니다

-> double 자료형인 x와 y값을 사용하여 temp를 계산해야하므로 double temp로 수정

 

3. 기존에 풀이했던 "11758번: CCW" 문제와 "2166번: 다각형의 면적" 문제에 대한 복습 필요

[C] 백준 - 11758번: CCW

[C] 백준 - 2166번: 다각형의 면적

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

 

풀이

#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;
    }
}

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;
    }
}

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;
}

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