bzoj 5099 [POI2018]Pionek 计算几何 极角排序
生活随笔
收集整理的這篇文章主要介紹了
bzoj 5099 [POI2018]Pionek 计算几何 极角排序
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
[POI2018]Pionek
Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 269 Solved: 80
[Submit][Status][Discuss]
Description
在無限大的二維平面的原點(0,0)放置著一個棋子。你有n條可用的移動指令，每條指令可以用一個二維整數向量表
示。每條指令最多只能執(zhí)行一次，但你可以隨意更改它們的執(zhí)行順序。棋子可以重復經過同一個點，兩條指令的方
向向量也可能相同。你的目標是讓棋子最終離原點的歐幾里得距離最遠，請問這個最遠距離是多少？
Input
第一行包含一個正整數n(n<=200000)，表示指令條數。
接下來n行，每行兩個整數x,y(|x|,|y|<=10000)，表示你可以從(a,b)移動到(a+x,b+y)。
Output
輸出一行一個整數，即最大距離的平方。
Sample Input
5
2 -2
-2 -2
0 2
3 1
-3 1
2 -2
-2 -2
0 2
3 1
-3 1
Sample Output
26
HINT
確定一個方向，然后再該方向上投影為正的都需要計算，
所以這個極角排序后即可O（n），兩個指針，這個是基本操作，這里有個性質，方向的話需要將其及其反方向都加進去。
然后去操作一波，就是180半面上的都加在一起就可以了。
總結
以上是生活随笔為你收集整理的bzoj 5099 [POI2018]Pionek 计算几何 极角排序的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 畅通工程续（HDU 1874）附上超详细
- 下一篇： 化工防爆气象站：采取防爆设计以保障化工厂