(BOJ 2650 교차점개수) 주어진 문제 변형 (단순화) & 수식화 전략

두 점이 쌍으로 주어지는데, 두 점을 직선 또는 곡선으로 마음대로 이을 수 있다. 교차점이 최소가 되게 만들어야 한다.

 

Sol 1) (WA) 수학적 접근

각 점을 좌표평면 위 좌표로 변환하고, 직선의 기울기랑 y절편 구해서 교점 구하는 식으로

 

문제점1. 기울기가 무한 소수점 double로 나오는 경우, 교차점이 정확히 구해지지 않을 수 있음
문제점2. 위 그림의 별표 처럼, 한 변에 두 점이 모두 붙어 있는 경우 처럼 교점을 구하기 힘든 경우가 있는데,

이런 예외가 한 두가지가 아니고 일일히 처리해주기 힘듦

 

=> 구현하다가 포기

 

---

Sol 2) 직사각형 위 좌표 -> 원 위의 좌표 ('원'이라고 표현했는데, 왼쪽 위 시작점에서 얼마나 먼지 '거리')

 

직사각형 왼쪽 위 꼭짓점을 시작점으로 해서, 각 점이 시작점에서 얼마나 멀리 떨어져있는지 나타낼 수 있다.

이렇게 하면, 점들의 상대적인 위치 정의가 가능!

→ 점들을 이어서 만든 직선의 교차 여부를 훨씬 더 쉽게 판별 가능

 

위 그림에서 a < c < b < d 일때, 두 직선의 교차 여부를 어떻게 확인할 수 있을까?

c가 a, b 사이에 있고, d가 a, b 바깥에 있으면 된다.

 

수식으로 표현하면 다음과 같다.

a < c < b && b < d

 

종만북에서 말하는

- 문제의 단순화

- 수식화

전략을 잘 보여주는 예제라고 생각된다.

 

 

아이디어는 다음 블로그 참고
https://hangjo-o.tistory.com/27

[백준/Python] 2650 - 교차점개수

 

구현은 다음 블로그 참고 (요 블로그 코드는 사실 틀렸음; 직사각형 길이를 51로 제한해서)
https://degurii.tistory.com/123?category=755814

 

 

+) 참고로 변환할 때, 직사각형의 width, height가 필요할 것 같은데, 문제에서 주어져있지 않다.

아마 직접 구해야 하는 듯?

(Q. width height 없이도 좌표 변한 가능할까?)