私は codeforces.ru から問題を解決していましたが、問題を解決できず、社説では凸包のトリックを使用するように言われました。
凸包のトリックに関するこの記事を読んでみましたが、理解できませんでした。
凸包のトリックとは何か正確に教えてもらえますか?
前もって感謝します。
5808 次
2 に答える
5
行のセット Y i = A i * X + B iがある場合、問題は、指定された X の最小の Y iを見つけることです。単純に、この X のすべての Y iを評価して、最小のものを選択することができます。しかし、X の一連の値を評価したい場合は、Y iが交差する場所をより適切に判断し、交差間の間隔ごとにどの Y iが最小かを判断できます。次に、X を指定して、対応する区間を選択し、その区間で最小の Y iのみを評価します。
(緑の線で視覚化: http://wcipeg.com/wiki/File:Convex_hull_trick1.png )
于 2013-07-24T13:29:01.607 に答える