時間限制 2000 ms ・ 記憶體限制 256 MB
題目描述
有一間 10000×10000 的正方形房間，左下角為 (0,0)、右上角為 (10000,10000)。內部有若干以簡單多邊形圍成的隔間，隔間邊界互不相交，但一個隔間可以完整包含另一個。
捕食者每次最多跳過一道隔間牆。給定起點與終點，求到達終點至少須跳過幾道牆。起點與終點保證不在任何隔間邊界上。
輸入格式
第一行為 T（T ≤ 20）。每筆先有 n（n ≤ 20），接著 n 行描述多邊形：先給邊數 S（S ≤ 10），再按邊界順序給 S 對 x y 座標。之後有查詢數 Q，再接 Q 行 x₁ y₁ x₂ y₂，表示起點與終點。所有隔間嚴格位於房間內。
輸出格式
每筆先輸出 Case k:，k 從 1 起。其後每個查詢輸出最少跳牆次數，占一行。
範例測資
範例輸入 1
2 3 4 1 1 5 1 5 5 1 5 4 2 2 4 2 4 4 2 4 3 7 7 10 10 7 10 1 3 3 8 9 1 4 1 1 10 1 10 10 1 10 2 2 2 100 100 100 100 2 2
範例輸出 1
Case 1: 3 Case 2: 1 1
請先登入後再提交程式碼
討論與題解
載入討論區…