[일반] 문제 하나만 질문드립니다.

[익명(14.54)]

왼쪽 아래를 (0, 0)이라고 가정하고 

빨간 선은 (x1, y1) (x2, y2) 들을 각각 이은 선들입니다.

그림처럼 빨간 선들은 항상 x축 혹은 y축과 평행을 이룹니다.

각 빨간 선들과 거리의 합이 최소(하늘색 선들의 합)인 좌표를 찾아야하는데 풀이 방법을 도저히 모르겠네요

어떤식으로 풀어야하나요?

[tktkc(211.36)]

x축과 평행한 애들, y축과 평행한 애들을 나눠서 생각하면 웰노운 그리디입니다

[익명(14.54)]

흠 나눈담에 어떻게해야되는지 잘모르겟습니다만 ㅠ

[익명(182.231)]

y축과 평행한직선들 따로 x축과 평행한 직선들 따로 생각해보셈 1차원에서는 매우 쉬운 문제고 2차원도 마찬가지 - dc App

[익명(115.23)]

x1 x2가 같으면 x와의 거리 y1 y2가 같으면 y와의 거리가 최소 아님..?

[익명(14.54)]

빨간선들은 개수가 엄청많습니다!

[익명(183.100)]

선들을 각각 점으로 분해해서 생각하고 가로,세로 따로따로 중앙인점 구하면 될거같은데

[익명(59.13)]

빨간선이 몇갠진 몰라도 O(N)이 안될정도로 많을건 아닐거아님

[익명(59.13)]

아 정렬 안되어있으면 O(NlogN)까진 가능해야겠네

[익명(14.54)]

풀이 방법이 정확히 어떤지좀..

[익명(222.112)]

ㅈㄴ어려운 문제같은데.. 무한히 긴 직선이 아니라 선분이잖어. 각 선분별로 거리함수 만들어서 이분탐색 x-y축 번갈아가면서 써야할듯

[익명(222.112)]

x랑 y 최소 최댓값 차이를 각각 Mx My라 하면 시간복잡도는 O(N * log(Mx + My))일듯

[익명(175.195)]

ㄹㅇ ㅈㄴ어려운 문제인듯

[익명(211.36)]

선분이 축에 수직한거임?

[blobfacepalm(tlsdydaud1)]

거리의 기준이 직선거리랑 택시거리 중에 어떤쪽임? 이것도 체크해야 할것같은데

[익명(14.54)]

아 그 택시거리임

[익명(14.54)]

택시거리가 그 꺾이는거 맞지?

[blobfacepalm(tlsdydaud1)]

ㅇㅇ