問題文
この問題は、50点を目安に頑張ってください。
ただし、チャレンジしたい人は100点を目指して頑張ってください。
JOI 君は、N*N のケーキを買った。
そのケーキには、K 個のイチゴが乗っている。マス(Xi,Yi)に置かれている。
このケーキの一部分(長方形でなければならない)を取り出して、それに含ま れるイチゴの個数が K/2 個となるようにしたい。
そのような長方形の選び方は何通りあるか
ただし、イチゴは同じマスに 2 つある場合もあります
入力の終わりは、ゼロ 2 つの行で表される。
ただし、テストケースはランダムである。
制約
1≦N≦ 3,5001≦K≦150,000
部分点
5 点分のテストケースでは、1≦N≦10 を満たす。10 点分のテストケースでは、1≦N≦100 を満たす。
25 点分のテストケースでは、1≦N≦300 を満たす。
50 点分のテストケースでは、1≦N≦1,000 を満たす。
100点分のテストケースでは、1≦N≦3,500 を満たす。
入力例
6 4 2 2 2 5 5 2 5 5 10 1 10 10 10 2 9 10 10 9 0 0
出力例
96 0 198
------------------ [ ][ ][ ][ ][ ][ ] ------------------ [ ][1][ ][ ][3][ ] ------------------ [ ][ ][ ][ ][ ][ ] ------------------ [ ][ ][ ][ ][ ][ ] ------------------ [ ][2][ ][ ][4][ ] ------------------ [ ][ ][ ][ ][ ][ ] ------------------[1]と[2]を含む場合、X座標4通り、Y座標6通りの合計24通りが考えられる。
[1]と[3]、[2]と[4]、[3]と[4]についても同じことが言えるため、24*4=96通りが答え。