Tree-Lined Streets

第一篇文章就獻給了World Final的題目......，而這題其實沒有想像中的難。

題目出處： ACM-ICPC World Final 2004 

題目大意：給出一個小鎮的街道分布 ( 二維座標，且道路均為直線 ) ，要將小鎮綠化，因此要種樹。而種樹有兩個規則：

　　1. 每一條道路上每50公尺才種一棵 ( 生長空間和花費控制 )

　　2. 若兩條道路有相交，則距離相交點25公尺內都不能種樹 ( 怕妨礙視線 )

整理題目敘述得知：任兩條道路不會有端點重合，而且不存在三線共交點，精度部分在0.001就可以了。輸出最多能種幾棵樹。

解題方法：模擬所有道路相交情況 ( 紀錄相交的點和道路起點距離 )，對每一線段所有交點的距離排序後，針對每一小段進行計算，用貪心法處理。若可種植範圍為正數 則數量最多為 [ 可種植範圍 / 50 ] + 1 棵 。 

代碼如下：