이분탐색을 사용합니다.

A, B는 각각 2차원 평면 위 점들의 집합이라고 합니다.(A의 크기 = 3, B 의 크기 = 100만)

A에 있는 한 점을 p라고 합니다.

B에 있는 점들 중에서 p 보다 왼쪽에 있는 점들의 집합을 B_left, 오른쪽에 있는 점들의 집합을 B_right라고 합니다. (이분 탐색을 통해서 가능합니다. 이때 사용되는 p의 횟수는 log(100만) 이므로 100만보다 훨씬 적습니다.)

(B에 있는 모든 점 q에 대해서 abs(p.x - q.x) 의 합)

= (B_right에 있는 모든 점 q에 대해서 -(p.x - q.x) 의 합) + (B_left에 있는 모든 점 q에 대해서 (p.x - q.x) 의 합)

= (B_right에 있는 모든 점 q의 갯수)*(-p.x) + (B_right에 있는 모든 점 q에 대해서 q.x의 합) + (B_left에 있는 모든 점 q의 갯수)*(p.x) +(B_right에 있는 모든 점 q에 대해서 -q.x 의 합)

= ((B_left에 있는 모든 점 q의 갯수)-(B_right에 있는 모든 점 q의 갯수))*(p.x) + (B_right에 있는 모든 점 q에 대해서 q.x의 합) + (B_right에 있는 모든 점 q에 대해서 -q.x 의 합)

이렇게 p.x 값을 한번만 써서 x 축 방향 abs 합을 구할 수 있습니다. 마찬가지로 위 아래로 나눠서 y축방향도 구할 수 있구요.

이걸 X에 있는 점 3개에 대해서 전부 하고 그중 제일 작은걸 고르면 됩니다.

3개중 딱 하나를 고르는게 아니라.. 100만개 B에

대해 각각 3개 점 중 하나씩 100만번을 구해야

하는 문제입니다 35만개 제한도 그래서 나왓고요

아하 이제 문제가 이해가 됬습니다.

그리디로 충분하지 않을까요? 먼저 x0, x1, x2와 y 사이의 거리를 전부구하고 x1,과 x2 의 거리는 둘중에 최소값을 구합니다.

D0_i = abs(x[0][0]-y[i][0]) + abs(x[0][1]-y[i][1])

D1_i = abs(x[1][0]-y[i][0]) + abs(x[1][1]-y[i][1])

D2_i = abs(x[2][0]-y[i][0]) + abs(x[2][1]-y[i][1])

D12_i = min(D1_i, D2_i)

D0_i가 D12_i 보다 작은 i가 35만 보다 적으면 그대로 min(D0_i, D12_i) 를 100만개에 대해서 합하면 되고, 만약 D0_i가 D12_i 보다 작은 i가 35만 보다 많으면 D0_i - D12_i 의 값으로 정렬을 해서 작은것부터 35만개를 고르면 어떨까요?

kokosoko 님 답변 감사드립니다.

근데 35만개 제약이 D0_i 뿐만 아니라 D1_i, D2_i 모두 해당되는 조건이라..

만약 D12_i 계산시에 D2_i 값보다 D1_i 값이 더 작은게 많아서 D1_i 값만 40만개 반영했다고 하면 이것도 Fail 입니다..

결론적으로 D0_i, D1_i, D2_i 모두 각각 35만개 이하로 사용하여 최종 100만개 더한 값을 최소화 시키는게 목적입니다..

생각보다 어려운 문제였네요..

이런식으로 몇개 미만 이라던가 하는 제한조건이 걸려있는 최적화 문제에 사용되는 일반적인 해결 방법으로 Integer prgramming이 있긴한데.. 이 방법은 직접 구현하기에는 어렵고 구현 방식이나 문제에 따라서 성능이 크게 차이가 나서 이 문제의 해답이라고 하기에는 조금 그러네요..

혹시 그럴듯한 방법을 찾으시면 댓글로 알려주실수 있을까요? 저도 많이 궁금하네요!