주어진 점들 중 최대 맨해튼 거리(Manhattan Distance)를 빠르게 찾는 방법

https://atcoder.jp/contests/abc178/tasks/abc178_e E - Dist MaxAtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jp   n개의 점이 주어질때, 이들 쌍으로 만들 수 있는 가장 긴 맨해튼 거리는? n이 최대 20만이기 때문에 O(N2)으로 직접 비교할 수는 없다 두 점 (xi,yi), (xj,yj)에 대하여 맨해튼 거리는 |xi - xj| + |yi - yj| = A A는 xi,xj, yi,yj 사이 대소관계에 따라 다음과 같이 풀어낼 수 있다 1) $x_{i} >= x_{j}..

  • format_list_bulleted 애드 혹 알고리즘
  • · 2024. 10. 23.
  • textsms

모든 좌표까지 맨해튼 거리 합이 최소가 되는 위치를 구하는 방법

1. 모든 점까지 맨해튼 거리의 합이 최소가 되는 점의 위치? m차원의 n개의 점들 P1(x11,x12,...,x1m),...Pn(xn1,xn2,...,xnm)에 대하여, 이들까지 맨해튼 거리의 합이 최소가 되는 점 X의 좌표를 구하라고 한다면, 어떻게 구할 수 있을까? 정답은 n개의 점들을 1,2,...,m차원의 좌표 값에 대하여 정렬한 다음, 중앙값에 해당하는 점의 좌표 Pmedian이 된다. 직관적으로 쉽게 눈치챌 수 있기는 한데, 왜 그런지 생각해보자. 2. 증명 먼저 점들의 좌표가 합에 서로 영향을 주지 않는다는 점을 관찰하자. 예를 들어 (3,5), (4,2), (5,1)에 대하여 (x,y)까지 맨해튼 거리의 합은.. $|x-3| + ..

  • format_list_bulleted 기하학
  • · 2023. 8. 24.
  • textsms

모든 좌표 쌍의 맨해튼 거리의 합을 효율적으로 구하는 방법

1. 문제 21203번: Distance (acmicpc.net) 21203번: Distance The City of Manhattan is organized as a grid of streets and avenues, with streets running in the North-South direction and avenues running in the East-West direction. Streets are numbered from East to West starting from 1, and avenues are numbered from N www.acmicpc.net 2. 풀이 n 제한이 20만이라 모든 좌표쌍 일일이 정해서 거리를 구해보는 방법으로는 어림도 없다 https://www.geeksf..

  • format_list_bulleted 기하학
  • · 2023. 8. 24.
  • textsms