[BOJ] 17387 - 선분 교차 2

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

BOJ - 선분 교차 2

문제 유형: 선형대수, 수학, 기하학

문제 난이도: Gold II

시간 제한: 0.25초

메모리 제한: 512MB

 

문제

2차원 좌표 평면 위의 두 선분 L1, L2가 주어졌을 때, 두 선분이 교차하는지 아닌지 구해보자. 한 선분의 끝 점이 다른 선분이나 끝 점 위에 있는 것도 교차하는 것이다.

L1의 양 끝 점은 (x1, y1), (x2, y2), L2의 양 끝 점은 (x3, y3), (x4, y4)이다.

 

입력

첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x4, y4가 주어진다.

 

출력

L1과 L2가 교차하면 1, 아니면 0을 출력한다.

 

풀이

처음에는 직선의 방정식을 이용해서 풀려고 했으나.. 부동소수점 때문인지 아니면 내가 케이스를 잘 못 쪼갠건지 계속 허덕였다.

어떻게 푸는가 찾아봤더니.. ccw(counter clockwise)라는 알고리즘을 이용해야 한다고 한다.

기하학 및 선형대수에 너무 약하다..

ccw를 통해서, 세 점에서 두 벡터 AB, AC에 대한 외적의 방향을 알 수 있는데, 벡터 AB에 대한 AC의 상대적인 방향에 대한 스칼라 값을 가진다.

오른손 법칙에 의해,

외적값이 양수면 반시계방향,

외적값이 음수면 시계방향,

외적값이 0이면 평행하다.

 

(a, b, c)와 (a, b, d)의 곱이 음수라면, c와 d는 벡터 AB기준으로 갈라져 있음을 의미한다.

(c, d, a)와 (c, d, b)의 곱 역시 음수라면, a와 b는 벡터 CD기준으로 갈라져 있음을 의미한다.

즉, 이렇게 교차하는지에 대해 확실히 알 수 있다.

그러나, 만약 cca값이 0으로 나와서 방향이 같을 수도 있다.

이럴 때에는, 접점을 찾으면 되는데, cca(a, b, c)가 0인 경우, 벡터 AB에 대해서 c가 선분 AB위에 있음을 확인하면 된다.

다른 총 4가지에 대해서도 적용해서 하나라도 맞으면 교차한다.

이외의 나머지 모든 경우는 교차하지 않는 경우이다.

 

코드

C++

#include <bits/stdc++.h>
#define ll long long
#define pll pair<ll, ll>
using namespace std;

int ccw(pll &a, pll &b, pll &c) {
  ll res = (b.first - a.first) * (c.second - a.second) -
           (b.second - a.second) * (c.first - a.first);
  if (res > 0)
    return 1;
  if (res < 0)
    return -1;
  return 0;
}

bool isPoint(pll &p1, pll &p2, pll &p) {
  return min(p1.first, p2.first) <= p.first &&
         p.first <= max(p1.first, p2.first) &&
         min(p1.second, p2.second) <= p.second &&
         p.second <= max(p1.second, p2.second);
}

bool isIntersect(pll &a, pll &b, pll &c, pll &d) {
  int ccw1 = ccw(a, b, c);
  int ccw2 = ccw(a, b, d);
  int ccw3 = ccw(c, d, a);
  int ccw4 = ccw(c, d, b);

  if (ccw1 * ccw2 < 0 && ccw3 * ccw4 < 0)
    return true;

  if (ccw1 == 0 && isPoint(a, b, c))
    return true;
  if (ccw2 == 0 && isPoint(a, b, d))
    return true;
  if (ccw3 == 0 && isPoint(c, d, a))
    return true;
  if (ccw4 == 0 && isPoint(c, d, b))
    return true;
  return false;
}

int main() {
  pll a, b, c, d;
  cin >> a.first >> a.second >> b.first >> b.second;
  cin >> c.first >> c.second >> d.first >> d.second;

  cout << (isIntersect(a, b, c, d) ? 1 : 0) << "\n";

  return 0;
}