[BOJ] 2650. 교차점개수

1일 1PS 2일차!

문제

---

골드 4

발상은 쉬웠지만 변환에서 시간이 많이 소요되었다. 변환을 잘하자!

포인트

---

• a, b 를 잇는 선분과 c, d 를 잇는 선분이 교차한다는 것은 a, b 로 분리되는 두 영역에 c, d 가 하나씩 존재한다는 것이다.

• c, d 가 분리된 영역에 나뉘어 존재하는 지를 판별해야한다.

• 좌표가 순서대로 되어있지 않기에 변환이 필요하다.
  • 처음에는 거리 한 변의 최대 길이를 못봐서 부등호로 표현하느라 시간이 오래걸렸다.
  • 하지만 한 변의 최대 길이가 주어진다면 일련의 방법으로 줄세우기가 가능하다!

1. 변의 위치를 순서대로 매핑한 다음 한 변의 최대 길이 50 + 1 을 각 변에 할당한다. 2번, 3번 반대 방향으로 증가하기에 끝에서 이동한 변 만큼 빼준다. 결국 부등호를 쓰기 위해 변환해서 줄세우기가 포인트
2. XOR 를 (stateA != stateB) 를 사용해서 표현 가능하다.

코드

---

n = int(input())

cross = [ 0 for _ in range(n // 2)]
points = []

mapping = {1: 0, 2: 2, 3: 3, 4: 1}
result = 0

for i in range(n // 2):
    x1, x2, y1, y2 = map(int, input().split())
    x1, y1 = mapping[x1], mapping[y1]

    x = x1 * 51 + x2
    y = y1 * 51 + y2
    if x1 >= 2:
        x += 51 - 2 * x2
    if y1 >= 2:
        y += 51 - 2 * y2

    x, y = max(x, y), min(x, y)

    for j in range(len(points)):
        point_x, point_y = points[j]
        if ((point_x < x) and (point_x > y)) != ((point_y < x) and (point_y > y)):
            result += 1
            cross[i] += 1
            cross[j] += 1
    points.append([x, y])

print(result)
print(max(cross))