Finále

A: Věže na šachovnici

Abys mohl odevzdávat úlohy, musíš se přihlásit nebo zaregistrovat

Nejsi finalista, takže se neobjevíš ve výsledcích.

Zadání (Řešení)

Mějme šachovnici o rozměrech N ⨯ N a na ní umístěných V šachových věží. Vaší úlohou je vypsat velikost (obsah) největšího obdélníku, který není ohrožován žádnou věží. V případě, že bude velikost šachovnice nulová (tj. N = 0) nebo bude ohrožené každé políčko, vypište nulu.

Věže se mohou klidně ohrožovat a také jich může více stát na jednom políčku. Pokud jich více okupuje to stejné místo, pak je klidně můžete brát jako jednu.

Souřadnice věží indexujeme od 0.

Tvar vstupu

Na vstupu máte na prvním řádku číslo T, počet testovacích vstupů v jednom souboru. Každý vstup vypadá tak, že na prvních dvou řádcích má čísla N a V, tedy velikost šachovnice a počet věží. Následuje V řádků (jeden pro každou věž) obsahující vždy dvojice čísel, x-ovou souřadnici věže a y-ovou.

Tvar výstupu

Pro každý testovací vstup vypište jediné číslo odpovídající obsahu největšího neohroženého obdélníku. Toto číslo se určitě vejde do 64bitového integeru.

Lehká verze

  • 0 < T ≤ 10
  • 0 ≤ N ≤ 1 000
  • 0 ≤ V ≤ 600
  • 0 ≤ x,y < N

Těžká verze

  • 0 < T ≤ 20
  • 0 ≤ N ≤ 109
  • 0 ≤ V ≤ 60 000
  • 0 ≤ x,y < N

Ukázkový vstup

3
5
3
0 0
0 0
0 1
5
2
0 0
4 4
5
3
0 0
2 0
0 1

Ukázkový výstup

12
9
6

Máš na to!

I ty můžeš vyhrát! Nebo to aspoň zkusit :)