題目 1950:
藍橋杯算法提高VIP-Tree-Lined Streets
時間限制: 2s
內(nèi)存限制: 192MB 提交: 2 解決: 0
題目描述
格林維爾的市議會最近對改善城市道路景觀進行了投票。為了讓城市增添一絲綠色，市議會決定在主要的大街兩旁種樹。由于想要初步預算這個城市改善計劃的費用，市議會想要知道會種多少樹。種樹的時候有以下兩條限制：
● 在一條大街上，每兩棵樹之間的距離至少為 50 米。這是為了給樹提供充足的生長空間，同時把費用控制在合理的范圍內(nèi)。
● 出于安全考慮，樹與它所在的大街上十字路口的距離應該不少于 25 米。這是為了保證司機能夠輕松地看到其他靠近十字路口的人。交通安全決不能因為能見度降低而被削弱。
在這個項目中的所有大街都是筆直不彎曲的。
市議會想知道在這兩個條件下能種的樹有幾棵。
輸入格式
第一行一個整數(shù) n，表示地圖中大街的數(shù)量。接下來 n 行，每行四個整數(shù) x1, y1, x2, y2，表示一條從 (x1, y1) 到 (x2,y2) 的線段，描述一條大街。每條大街長度都是正數(shù)，且每個端點只落在一條大街上。
對于一條大街，相鄰的十字路口或端點的距離不會是 25 的倍數(shù)。更準確地，他們的距離與 25 的倍數(shù)的差不少于 0.001。在每個十字路口，恰好只會有兩條大街交叉。
輸出格式
輸出在上述特定條件下最多能種的樹的棵樹。
樣例輸入
3
0 40 200 40
40 0 40 200
0 200 200 0
提示
零基礎同學可以先學習
視頻課程，包含C/C++、Python、百練、藍橋杯輔導、算法數(shù)據(jù)結(jié)構(gòu)等課程，提供視頻講解以及配套習題，還有老師答疑，
點擊這里了解課程詳情