[백준17386_자바스크립트(javascript)] - 선분 교차 1

경이·2025년 5월 7일

𝑩𝑶𝑱 (𝒋𝒔)

목록 보기

302/325

🔴 문제

선분 교차 1

🟡 Sol

const fs = require('fs');
const path = process.platform === 'linux' ? '/dev/stdin' : 'input.txt';
const inputs = fs
  .readFileSync(path)
  .toString()
  .trim()
  .split('\n')
  .map((it) => it.split(' ').map(Number));

const [x1, y1, x2, y2] = inputs[0];
const [x3, y3, x4, y4] = inputs[1];

const CCW = (x1, y1, x2, y2, x3, y3) => {
  return (x2 - x1) * (y3 - y1) - (y2 - y1) * (x3 - x1);
};

const a = CCW(x1, y1, x2, y2, x3, y3);
const b = CCW(x1, y1, x2, y2, x4, y4);

const c = CCW(x3, y3, x4, y4, x1, y1);
const d = CCW(x3, y3, x4, y4, x2, y2);

if (a * b <= 0 && c * d <= 0) console.log(1);
else console.log(0);

🟢 풀이

⏰ 소요한 시간 : -

선분 교차를 판별하는 문제다.
선분 교차는 CCW라는 알고리즘으로 알아낼 수 있다.
CCW는 세 점이 이루는 방향을 계산하는 알고리즘이다.

위와 같이 1번점과 2번점이 있을 때 그 두 점을 이은 상태에서, 나머지 하나의 점이 반시계 구역인지, 시계구역인지를 판단하는 방식이 CCW이다.

이 때 벡터의 외적을 통해서 세 점이 이루는 방향을 알 수 있다.

A × B > 0: A에서 B로 가는 방향이 반시계 방향
A × B < 0: A에서 B로 가는 방향이 시계 방향
A × B = 0: A와 B가 같은 방향이거나 일직선상에 존재

즉, 각 선분에 대해 다른 선분의 두 끝점이 서로 다른 방향에 위치해, 하나는 시계방향, 하나는 반시계 방향이 나와 두 결과값의 곱이 음수가 뒤어야 선분이 교차하는 것이다.

const a = CCW(x1, y1, x2, y2, x3, y3);
const b = CCW(x1, y1, x2, y2, x4, y4);

const c = CCW(x3, y3, x4, y4, x1, y1);
const d = CCW(x3, y3, x4, y4, x2, y2);