투명한 선체 트릭이란 무엇입니까?

Question

나는 codeforces.ru에서 문제를 해결하고 있었지만 문제를 해결할 수 없었으며 사설에서는 볼록 선체 트릭을 사용한다고 말했다 (http://codeforces.com/blog/entry/7785).

나는 convex hull trick (wcipeg.com/wiki/Convex_hull_trick)에 대해이 기사를 읽으려고했지만 이해할 수 없었다.

아무도 볼록 선체 트릭이 무엇인지 정확히 알 수 있습니까?

미리 감사드립니다. 당신이 Y _{라인의 세트가있는 경우}

Answer 1

내가는 = A _내가 * X + B 내가, 다음 문제는 주어진 X의 순진에 대한 Y _내가 작은을 찾는 _{, 당신이 평가하기 위해 시도 할 수 이 X에 대해 모두 Y i을 선택하고 가장 작은 것을 선택하십시오. 그러나 X에 대한 일련의 값을 평가하려는 경우 Y i이 교차하는 위치를 더 잘 결정할 수 있으며 교차점 사이의 각 간격에 따라 Y i이 가장 작은 값을 결정합니다. 그런 다음 X가 주어지면 해당 간격을 선택하고 해당 간격에서 가장 작은 Y i 만 평가합니다.}

Answer 2

한다고 가정 우리가 M 라인 (http://wcipeg.com/wiki/File:Convex_hull_trick1.png 여기에 녹색 선으로 가시화)

. 임의의 점 x가 주어진다면, M 개의 선은 y (x) 값의 관점에서 어떤 순서로 존재합니다. 라인 순서는 2 개의 라인 순서가 항상 바뀌는 교차점이 생길 때까지 보존됩니다.

X 축을 스캔하고 각 교차점에 대한 정렬 선 순서를 알고 있으면 X 축에서 각 교차점 (다른 교차점에서 다른 교차점까지)에 대한 선 순서를 제공하는 데이터 구조를 얻습니다. 그게 ...