2121 넷이 놀기

가로 길이 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개가 다 있는지 이분탐색으로 할 게 아니라 기준점을 네모의 왼쪽위라고 지정해놓고 나머지 세 점만 구하면 된다.

생각을 하자