入隊後處男文

2年後既我奇蹟地入左隊... 感覺唔係好真實
知道自己實力好弱, 唔想拖累隊友, 所以我諗比起學業, 提升自己比賽水平更重要吧..

見david做緊 一條visibilty 既難題(?) moth...
GG 叫我做另一題相同意味但易少少既: A Safe Way
http://poj.org/problem?id=2966
題意簡單, 算法則要做過才知道吧..而且CODING上亦好麻煩

題意:  given polygon (maybe convex!) ,任意2點, a,b,  find shortest path from a to b, path cannot go through the polygon (but can go along the edges)

算法如下:
1. build visibility graph for vertex of polygon & a & b
2. shortest path on the graph

Coding上就好麻煩了..
首先build visibility graph...請教左GG之後, 我既實際做法係
1. for 每pair 點, i 同 j  
        check mid - point 係咪 completely inside polygon (係edge上唔算)
        呢度要用上 sum-of-angle 黎check as polygon maybe convex, 係edge上既直接return false
2. 如果pass 1, check intersection
--> proper intersection: 當然fail
--> improper intersection: 當 intersect 條edge 叫PQ (vector) ,如果intersect既當係[P.....Q) (無錯, 係唔包尾個個vertex, 原因....要畫下先解釋到)  則當有intersection , fail
--->else  PASS!

短短幾句, 已經要寫 spfa, intersection checking, sum of angle...
還好最後過到...原來錯個一棍係係feq( ) 入面少左個 ()...雖然唔知有咩所謂...嘛


Geom果然係無底深淵, 原來仲可以玩visibility graph + shortest path...


遲下再試下moth 吧...(進化版...n個polygon =[ )