• [1419] Largest Square

  • 时间限制: 1000 ms 内存限制: 65535 K
  • 问题描述
  • There is an N × N mosaic of square solar cells (1 ≤ N ≤ 2,000). Each solar cell is either good or bad. There are W (1 ≤ W ≤ 50,000) bad cells. You need to find the largest square within the mosaic containing at most L (0 ≤ L ≤ W) bad cells.
  • 输入
  • The input will begin with a number Z ≤ 20, the number of test cases, on a line by itself. Z test cases then follow. The first line of the test case contains three space-separated integers: N, W, and L. W lines follow, each containing two space-separated integers representing the coordinates of a location of the bad solar cells.
  • 输出
  • For each input instance, the output will be a single integer representing the area of the largest square that contains no more than L bad solar cells.
  • 样例输入
  • 1
    4 3 1
    1 1
    2 2
    2 3
    
  • 样例输出
  • 4
    
  • 提示
  • The mosaic is 4× 4, and contains the following arrangement of good and bad cells ('G' represents good, and 'B' represents bad): 
    BGGG
    GBBG
    GGGG
    GGGG
    
    Several 2× 2 squares at the bottom contain no bad solar cells, but all 3 × 3 squares contain at least two bad solar cells. 
  • 来源
  • 0 0
  • 操作

显示春菜