b342: 等高線
Tags : 掃描線
Accepted rate : 10人/11人 ( 91% ) [非即時]
評分方式:
Tolerant

最近更新 : 2015-07-16 17:36

Content
給一個等高線二維地圖,每一個等高線由一個平行兩軸的矩形構成,有 $N$ 個矩形、 $M$ 個地點,輸出每一個地點的所在位置高度,以及當前的所在矩形編號。


Input

有多組測資,

每一組第一行會有一個整數 $N$,表示接下來有多少個等高線。
接下來會有 $N$ 行,每行上會有四個整數 $(lx, ly, rx, ry)$。

接著一行一個整數 $M$,表示接下來有 $M$ 個點詢問,接下來會有 $M$ 行 $(x, y)$。

  • $1 \le N, M \le 32767$
  • $0 \le lx < rx \le 1,000,000, 0 \le ly < ry \le 1,000,000$
  • $-10,000,000 \le x, y \le 10,000,000$
Output
每組第一行,按照輸入順序輸出每條等高線高度,接著輸出 $M$ 行詢問所在的等高線編號。
Sample Input #1
7
0 0 10 10
1 1 9 2
1 3 9 7
2 4 4 6
5 4 6 5
7 5 8 6
1 8 9 9 
6 
3 5
6 6
7 4
9 1 
2 4 
-1 -1 
Sample Output #1
1 2 2 3 3 3 2
3
2
2
1
3
-1
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (25%): 1.0s , <1M
公開 測資點#1 (50%): 1.0s , <1M
公開 測資點#2 (25%): 1.0s , <1M
Hint :
Tags:
掃描線
出處:
[管理者:
morris1028 (碼畜)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」