가로 길이 A, 세로 길이 B인 직사각형 가지수
A(0,0)
B(2,0)
C(0,3)
D(2,3)
E(4,0)
F(4,3)
N : 50만개 점
A : 1000
B : 1000
점 좌표 - 10^9 ~ 10^9
1. 완전탐색
NC4 해서 주어진 점 N개 중에 4개를 고를 수 있는 경우 전체 확인
6C4 = 6 * 5 / 2 * 1
50만C4 = 너무 커짐 불가능
2. 어떻게 최적화를 할 것인가?
만약에 특정 점(K)이 정해지면 K점에서 만들 수 있는 사각형은 정해져있음
(KX, KY) (KX + A, KY) (KX, KY + B) (KX + A, KY + B)
(KX, KY) (KX - A, KY ) (KX , KY + B) (KX - A, KY + B)
(KX, KY) (KX - A, KY) (KX - A, KY - B) (KX , KY - B)
(KX, KY) (KX + A , KY) (KX , KY - B) (KX + A, KY - B)
(0 , 3) ( 2 , 3 ) (0, 6) (2 , 6)
C D ? ㅅㅂ 없는데?
(0, 3 ) (-2
없음
없음
(0 , 3 ) ( 2, 3) (0, 0) (2, 0)
C D A B
좌표들을 오름차순으로 정렬해놓고
이분탐색해서 나오는 값을 기준점으로 두고
그 기준점에서 만들 수 있는 사각형 네 개 구하기?
근데 기준점에서 만들 수 있는 사각형 좌표를 가지고 있는지 안가지고 있는지 어떻게 구할 수 있지?
근데 어떻게 할건데 ?
-----
(KX, KY) (KX + A, KY) (KX, KY + B) (KX + A, KY + B)
(KX, KY) (KX - A, KY ) (KX , KY + B) (KX - A, KY + B)
(KX, KY) (KX - A, KY) (KX - A, KY - B) (KX , KY - B)
(KX, KY) (KX + A , KY) (KX , KY - B) (KX + A, KY - B)
이렇게 8개가 다 있는지 이분탐색으로 할 게 아니라 기준점을 네모의 왼쪽위라고 지정해놓고 나머지 세 점만 구하면 된다.
생각을 하자
