2008年9月26日 星期五

837 Light and Transparencies

題目網頁:http://acm.uva.es/problemset/v8/837.html

因為題目有提到,沒有垂直 X 軸的線 (同一條線的 x1 != x2),所有 film 的兩端也不會重疊 (每個 x 都是獨一無二的點),所以就不必管 y ,將所有的 x 作排序後,再做計算,看看跟哪些 film 有重疊,來計算 r 是多少,不同 segment 的判斷,是由兩端的 x 值來決定,而不是 r ,討論區裡的 sample input 有些是錯誤的,沒有什麼特殊的 input ,不要想太多就可以 AC 了 。