#include "soccer.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<vector<int>> ps_h, ps_v;
bool gethrange(int l, int r, int y)
{
if (l > r) swap(l, r);
return ps_h[y][r + 1] - ps_h[y][l];
}
bool getvrange(int l, int r, int x)
{
if (l > r) swap(l, r);
return ps_v[x][r + 1] - ps_v[x][l];
}
int biggest_stadium(int N, vector<vector<int>> F)
{
int res = 0;
ps_h = ps_v = vector<vector<int>>(N, vector<int>(N+1));
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
ps_h[i][j + 1] = ps_h[i][j] + F[i][j];
ps_v[i][j + 1] = ps_v[i][j] + F[j][i];
}
}
int top;
int topl, topr;
for (int i = 0; i < N; i++)
{
if (ps_h[i][N] == N) continue;
for (int j = 0; j < N; j++)
{
if (F[i][j]) continue;
if (ps_h[i][j + (N - ps_h[i][N])] - ps_h[i][j])
return -1;
top = i;
topl = j;
topr = j + (N - ps_h[i][N] - 1);
break;
}
break;
}
int btm;
int btml, btmr;
for (int i = N-1; i >= 0; i--)
{
if (ps_h[i][N] == N) continue;
for (int j = 0; j < N; j++)
{
if (F[i][j]) continue;
if (ps_h[i][j + (N - ps_h[i][N])] - ps_h[i][j])
return -1;
btm = i;
btml = j;
btmr = j + (N - ps_h[i][N] - 1);
break;
}
break;
}
int lft;
int lft_up, lft_dwn;
for (int i = 0; i < N; i++)
{
if (ps_v[i][N] == N) continue;
for (int j = 0; j < N; j++)
{
if (F[j][i]) continue;
if (ps_v[i][j + (N - ps_v[i][N])] - ps_v[i][j])
return -1;
lft = i;
lft_up = j;
lft_dwn = j + (N - ps_v[i][N] - 1);
break;
}
break;
}
int right;
int right_up, right_dwn;
for (int i = N-1; i >= 0; i--)
{
if (ps_v[i][N] == N) continue;
for (int j = 0; j < N; j++)
{
if (F[j][i]) continue;
if (ps_v[i][j + (N - ps_v[i][N])] - ps_v[i][j])
return -1;
right = i;
right_up = j;
right_dwn = j + (N - ps_v[i][N] - 1);
break;
}
break;
}
if (!(lft_up >= right_up && lft_dwn <= right_dwn) && !(lft_up <= right_up && lft_dwn >= right_dwn))
return -1;
int v = max(max(lft_up, right_up), min(lft_dwn, right_dwn));
if (!(topl >= btml && topr <= btmr) && !(topl <= btml && topr >= btmr))
return -1;
int h = max(max(topl, btml), min(topr, btmr));
int cnt = 0;
for (int x = 0; x < N; x++)
{
for (int y = 0; y < N; y++)
{
if (F[y][x])
continue;
cnt++;
if (gethrange(x, h, y))
return -1;
if (getvrange(y, v, x))
return -1;
}
}
for (int x = 0; x < N; x++)
{
for (int y = 0; y < N; y++)
{
if (F[y][x])
continue;
{
bool b1 = getvrange(y, lft_up, x) || gethrange(x, lft, lft_up);
bool b2 = getvrange(y, lft_up, lft) || gethrange(x, lft, y);
if (b1 && b2)
return -1;
}
{
bool b1 = getvrange(y, right_up, x) || gethrange(x, right, right_up);
bool b2 = getvrange(y, right_up, right) || gethrange(x, right, y);
if (b1 && b2)
return -1;
}
{
bool b1 = getvrange(y, lft_dwn, x) || gethrange(x, lft, lft_dwn);
bool b2 = getvrange(y, lft_dwn, lft) || gethrange(x, lft, y);
if (b1 && b2)
return -1;
}
{
bool b1 = getvrange(y, right_dwn, x) || gethrange(x, right, right_dwn);
bool b2 = getvrange(y, right_dwn, right) || gethrange(x, right, y);
if (b1 && b2)
return -1;
}
{
bool b1 = getvrange(y, top, topl) || gethrange(x, topl, y);
bool b2 = getvrange(y, top, x) || gethrange(x, topl, top);
if (b1 && b2)
return -1;
}
{
bool b1 = getvrange(y, top, topr) || gethrange(x, topr, y);
bool b2 = getvrange(y, top, x) || gethrange(x, topr, top);
if (b1 && b2)
return -1;
}
{
bool b1 = getvrange(y, btm, btml) || gethrange(x, btml, y);
bool b2 = getvrange(y, btm, x) || gethrange(x, btml, btm);
if (b1 && b2)
return -1;
}
{
bool b1 = getvrange(y, btm, btmr) || gethrange(x, btmr, y);
bool b2 = getvrange(y, btm, x) || gethrange(x, btmr, btm);
if (b1 && b2)
return -1;
}
}
}
return cnt;
}
