b555: 攻城掠地
Tags : 四分樹 樹套樹 窮舉加速 長條切割
Accepted rate : 9人/21人 ( 43% ) [非即時]
評分方式:
Tolerant

最近更新 : 2015-09-17 06:44

Content

背景

某 M 不小心讀了研究所,由於能力上的缺陷,大學經歷轉學考試,最後在研究所又讀了另一間大學,見了不少學校資工系生態。許多新生面對程式充滿了憧憬,卻在大一程式設計課程受到強烈的打擊。

某 M 正經歷心驚膽戰的研究生活,曾經聽教授說過「有些學生跑去讀了台清交研究所,只能在實驗室的黑暗角落度日,倒不如在本來大學做研究」這一句話帶給某 M 相當大的影響,到底外面的世界是如何?對於不被社會認可為精英的某 M,走進了陌生的研究所,難道是被推甄、考試系統騙了進去嗎?

在研究室聽了不少學長和師長的諫言,某 M 更堅信了那一句話「在你對社會做了什麼、影響了什麼,這時候才是有價值的。在此之前,你什麼都不是。若要說能走進這教室學習是因考試成績不錯,有時候那是運氣,恰好那些考試都符合你的胃口,別以為自己是永遠的菁英。」

題目描述

給定 $N \times M$ 的網格土地,每個土地上都有資源,接著會有 $Q$ 組詢問 $lx, ly, rx, ry$,每一組詢問將會掠奪平行兩軸的矩形內部資源,一旦取走土地上資源,土地將會變得貧乏。對於每個詢問回報有資源的土地座標,若有多個座標,請按照字典順序輸出。

Input

只有一組測資,測資第一行會有一個整數 $N, M$。

接下來會有一個整數 $Q$,表示接下來會有 $Q$ 行詢問。

對於每一行詢問有四個整數 $lx, ly, rx, ry$,表示矩形的左上角點、右下角點座標。

  • $1 \le N, M \le 1000$
  • $1 \le Q \le 100000$
  • $1 \le lx, \; rx \le N$
  • $1 \le ly, \; ry \le M$
Output

對於每個詢問輸出一行,第一個數字表示有多少資源個數 $S$,接下來有 $S$ 個座標按照字典順序輸出。

Sample Input
5 4
3
2 2 3 3  
2 3 4 4
3 3 4 4
Sample Output
4 (2, 2) (2, 3) (3, 2) (3, 3)
4 (2, 4) (3, 4) (4, 3) (4, 4)
0
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (20%): 1.0s , <1K
公開 測資點#1 (20%): 1.0s , <1M
公開 測資點#2 (20%): 1.0s , <1M
公開 測資點#3 (10%): 1.0s , <10M
公開 測資點#4 (20%): 1.0s , <10M
公開 測資點#5 (5%): 1.0s , <10M
公開 測資點#6 (5%): 1.0s , <10M
Hint :
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
=>
1 1 1 1
1     1
1     1
1 1 1 1
1 1 1 1
=>
1 1 1 1
1     
1 
1 1   
1 1 1 1
=>
1 1 1 1
1     
1 
1 1   
1 1 1 1
Tags:
四分樹 樹套樹 窮舉加速 長條切割
出處:
Morris開學迎新 [管理者:
morris1028 (碼畜)
]


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