C++ 仿Unity Vector模板(隨緣更新題解)
翻了差不多一個月Unity的C#的Vector2和Vector3,抄重構(gòu)了一份自己的實現(xiàn)(
先上代碼
特性
可以用cout cerr 直接輸出Vector2和Vector3
基本上直接對接Unity官方文檔,可以參閱https://docs.unity3d.com/550/Documentation/ScriptReference/Vector3.html
對于三維向量,增加了經(jīng)緯度轉(zhuǎn)換支持
可以在開頭的using FLOAT_ = 處指定精度
N維向量還在施工中
先上一篇題解:https://codeforces.com/contest/1468/problem/G

題目大意:給定一條高低不平的二維山路,太陽在第n個點之上H高度處,你需要求出從第一個點走到第n個點的過程中被太陽曬到的距離,忽略你的身高,山路如圖以xi,yi的形式給出。
關(guān)鍵點:想到極角排序
思路:我們考慮以太陽放出一條射線,逆時針掃過群峰,發(fā)現(xiàn)每個極值點可能會在前面掃過的點與后一個點之間的路徑產(chǎn)生一個投影,這個投影是太陽會照到的地方與照不到的地方的交點。我們求出這個交點,與前一個點算一下距離然后加入答案中。

畫圖不難發(fā)現(xiàn)投影點的順序與其與太陽連線的斜率有關(guān)
具體做法:將每個折線的點與太陽連線,算出這條線的斜率,并且依據(jù)斜率將點升序排序,然后遍歷這些點,算出每條線段與下一個投影點的投影產(chǎn)生的貢獻(xiàn),一旦有貢獻(xiàn),將投影點之后的線段記為待處理線段,往后迭代。
細(xì)節(jié):點與投影點與太陽共線時,要根據(jù)情況查看線段是否可以計入貢獻(xiàn)。所以排序的第二關(guān)鍵字最好是x坐標(biāo)。
模板代碼: