[백준 17386] 선분 교차 1 (C#, C++) - soo:bak

문제 링크

17386번 - 선분 교차 1

설명

2차원 좌표계에서 두 선분의 교차 여부를 판별하는 문제입니다.

문제의 조건에서 세 점이 일직선 위에 있는 경우는 없다 라는 조건이 있으므로,
2차원 좌표계를 기준으로, 두 선분이 같은 기울기로 겹쳐지는 경우에 대해서 배제하여도 됩니다.
따라서, 벡터의 외적을 통하여 외적 결과값들의 부호가 다른지에 대해서만 판별하면 되는 문제입니다.

과정은 다음과 같습니다.

각각의 선분을 임의의 방향성을 가진 벡터 로 취급하고,
한 선분과 다른 선분의 시작 / 끝 점을 외적한 후, 외적 결과값들의 부호를 확인합니다.

만약, 선분 A 를 기준으로 선분 B 의 시작점 과 선분 B 의 끝점 을 각각 외적하였을 때,
외적 결과값들의 부호가 다르다는 것은 선분 A 를 기준으로 선분 B 의 시작점 과 선분 B 의 끝점 은 다른 방향에 있다는 것을 의미합니다.
즉, 외적 결과값들의 부호가 다르다면, 두 선분은 교차합니다.

주의해야 할 점은 한 선분만을 기준으로 활용하면 안된다는 것입니다.
만약, 두 선분이 ㅡ ㅣ 의 모양처럼 존재하는 경우,
왼쪽 ㅡ 선분을 기준으로한 외적의 결과값들은 부호가 다르지만,
오른쪽 ㅣ 선분을 기준으로한 외적의 결과값들은 부호가 같습니다.

따라서, 두 선분 각각을 기준으로 모두 외적하여, 외적 결과값들의 부호를 확인해야 합니다.

이렇게 벡터의 외적을 이용하여 3개의 점의 방향성을 판단하는 알고리즘을 CCW 알고리즘 이라고도 합니다.
벡터의 외적, CCW 알고리즘 에 대한 자세한 설명은 여기 에서 확인하실 수 있습니다.

---

Code

[ C# ]

namespace Solution {
  class Program {

    static long CrossProduct((long, long) p1, (long, long) p2, (long, long) p3) {
      var ret = ((p2.Item1 - p1.Item1) * (p3.Item2 - p1.Item2)) - ((p2.Item2 - p1.Item2) * (p3.Item1 - p1.Item1));
      return ret;
    }

    static bool IsSameSign(long cp1, long cp2) {
      if (cp1 > 0 && cp2 < 0) return false;
      else if (cp1 < 0 && cp2 > 0) return false;
      else return true;
    }

    static void Main(string[] args) {
      var input = Console.ReadLine()!.Split(' ');
      var pntL1Begin = (long.Parse(input[0]), long.Parse(input[1]));
      var pntL1End = (long.Parse(input[2]), long.Parse(input[3]));
      input = Console.ReadLine()!.Split(' ');
      var pntL2Begin = (long.Parse(input[0]), long.Parse(input[1]));
      var pntL2End = (long.Parse(input[2]), long.Parse(input[3]));

      var cp1 = CrossProduct(pntL1Begin, pntL1End, pntL2Begin);
      var cp2 = CrossProduct(pntL1Begin, pntL1End, pntL2End);
      var cp3 = CrossProduct(pntL2Begin, pntL2End, pntL1Begin);
      var cp4 = CrossProduct(pntL2Begin, pntL2End, pntL1End);

      if (!IsSameSign(cp1, cp2) && !IsSameSign(cp3, cp4)) Console.WriteLine(1);
      else Console.WriteLine(0);
    }
  }
}

[ C++ ]

#include <bits/stdc++.h>

using namespace std;

#define x first
#define y second

typedef long long ll;
typedef pair<ll, ll> pll;

ll crossProduct(const pll& p1, const pll& p2, const pll& p3) {
  ll ret = ((p2.x - p1.x) * (p3.y - p1.y)) - ((p2.y - p1.y) * (p3.x - p1.x));
  return ret;
}

bool isSameSign(const ll& cp1, const ll& cp2) {
  if (cp1 > 0 && cp2 < 0) return false;
  else if (cp1 < 0 && cp2 > 0) return false;
  else return true;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  pll pntL1Begin, pntL1End, pntL2Begin, pntL2End;
  cin >> pntL1Begin.x >> pntL1Begin.y >> pntL1End.x >> pntL1End.y;
  cin >> pntL2Begin.x >> pntL2Begin.y >> pntL2End.x >> pntL2End.y;

  ll cp1, cp2, cp3, cp4;
  cp1 = crossProduct(pntL1Begin, pntL1End, pntL2Begin);
  cp2 = crossProduct(pntL1Begin, pntL1End, pntL2End);
  cp3 = crossProduct(pntL2Begin, pntL2End, pntL1Begin);
  cp4 = crossProduct(pntL2Begin, pntL2End, pntL1End);

  if (!isSameSign(cp1, cp2) && !isSameSign(cp3, cp4)) cout << 1 << "\n";
  else cout << 0 << "\n";

  return 0;
}