[기하학] 선분 교차1 (17386) (C++)

https://www.acmicpc.net/problem/17386

17386번: 선분 교차 1

 

 

1. 문제 개요

 

2차원 좌표 평면 위의 두 선분의 양 끝점이 주어졌을 때, 두 선분이 교차하는지 아닌지 구하는 문제.

 

 

2. 입출력

 

 

 

3. 문제 풀이

 

점 3개의 방향성을 나타내는 CCW 알고리즘을 사용하여 풀이 할 수 있다.

CCW 알고리즘은 세 점으로 아루어진 삼각형의 면적을 구하는 방법을 이용해서 방향성을 구하는 알고리즘이다.

세 개의 점이 시계 방향, 반시계 방향 또는 평행하게 놓여있는지 여부를 알 수 있다.

 

typedef struct {
    long long x, y;
}pii;
 
long long ccw(pii a, pii b, pii c)
{
    long long ans = (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
    
    if (ans < 0) return 1;
    else if (ans > 0) return -1;
    else return 0;
}

ans > 0: 반시계 방향

ans = 0: 일직선

ans < 0: 시계 방향

                                                              

 

4. 전체 코드

 

#include <algorithm>
#include <stdio.h>
#include <vector>
#include <cmath>
#include <iostream>

using namespace std;
//선분 교차1

typedef struct {
    long long x, y;
}pii;
 
long long ccw(pii a, pii b, pii c)
{
    long long ans = (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
    
    if (ans < 0) return 1;
    else if (ans > 0) return -1;
    else return 0;
}

int main(void)
{
    pii A, B, C, D;
    
    cin >> A.x >> A.y >> B.x >> B.y;
    cin >> C.x >> C.y >> D.x >> D.y;
    
    if((ccw(A, B, C)*ccw(A, B, D)<=0)&&(ccw(C, D, A)*ccw(C, D, B)<=0)){
        printf("1\n");
    } else{
        printf("0\n");
    }
}