07/04/2025 07:40:05

Рабочее место участника

Задачи

1816. Largest Square

Ограничения: время – 4s/8s, память – 128MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

There is an

$N\ times\ 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.

Sample Input

Sample Output

The mosaic is

$4\ times\ 4$ , and contains the following arrangement of good and bad cells ('G' represents good, and 'B' represents bad):

BGGG
GBBG
GGGG
GGGG

Several

$2\ times\ 2$ squares at the bottom contain no bad solar cells, but all

$3\ times\ 3$ squares contain at least two bad solar cells.

Source: Waterloo local contest 2011

25/06/2012	Лето 2012 - дорешивание (11G)
11/07/2012	Лето 2012 - 11 (G)