BOJ 25034 convex4gon

문제 링크:

문제 내용

다음의 명세를 충족하는 파이썬 함수 convex4gon을 작성하세요.

입력: 하나의 리스트 $L$ 이 주어집니다. $L$ 의 각 원소는 정수 2개의 튜플이며, 각 튜플은 $(x, y)$ 좌표를 나타냅니다. $L$ 의 길이는 1 이상 30 미만이고, 각 좌푯값의 절댓값은 1000 이하이며, 세 점이 일직선상에 있는 경우는 없습니다.
출력: $L$ 에서 네 개의 점을 골라 볼록 사각형을 만드는 방법의 수를 리턴합니다. 점의 순서만 다른 것은 같은 방법입니다.

문제 풀이

스포일러

어떤 네 점 $A, B, C, D$ 가 볼록 사각형을 이룬다는 것은 모든 꼭짓점에서 좌회전을 해야 한다는 것과 동치입니다. 모두 우회전인 경우는 중복으로 세어지므로 제외하며, 시작점이 서로 다른 것도 중복으로 세어지므로 모두 센 뒤 4로 나누어 주거나, 시작점이 항상 가장 작은 인덱스가 되도록 하는 방법 등을 사용할 수 있습니다.

좌회전 판정을 네 번 해야 하므로, CCW 알고리즘을 함수로 만든 뒤 $ABC$ , $BCD$ , $CDA$ , $DAB$ 에 대해 모두 판정하여 모두 참인 경우에 개수를 1 증가시켜 주면 됩니다.

Last updated on 2026년 1월 5일 17:58:47

BOJ 24697 Interesting Subsegments BOJ 25102 Airline