正常没有正方形的限制下，值为i的点个数4i
那么从0开始遍历，第一个不为4i的值就是min(x, y)
由于对称性我们姑且令x为这个值
我们先列举n*m=t的各种情况
对于一对n, m。我们已经知道n,m,x
再由于对称性，我们假设距离(x,y)最远的点在(n, m)。(当然也可能在(1,m))
现在知道了(n,m)到(x,y)为max(a[I])
列方程就能求出y了
然后再暴力验证就好了
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <map>
using namespace std;
const int N = 1e6 + 5;
const int INF = 0x3f3f3f3f;
typedef long long ll;
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
int A[N];
int mp[N];
int maxNum;
struct Line{
int k, b;
Line(int a=0, int _b=0):k(a), b(_b){}
int Count(int x1, int x2, int y1, int y2) {
int L = k*x1 + b;
int R = k*x2 + b;
if(L > R) swap(L, R);
x1 = L; x2 = R;
if(y1 < x1) {
if(y2 < x1) return 0;
else if(y2 <= x2)
return y2 - x1 + 1;
else return x2 - x1 + 1;
} else if(y1 <= x2) {
if(y2 <= x2)
return y2 - y1 + 1;
else return x2 - y1 + 1;
} else
return 0;
}
};
bool Test(int n, int m, int x) {
if(n < 2*x-1 || m < 2*x-1)
return false;
int y = n + m - maxNum - x;
if(y < x || m - y < x - 1)
return false;
// printf("%d %d\n", n, m);
for(int i = x; i <= maxNum; ++i) {
int all = 0;
int l1 = max(1, x - i);
int l2 = min(n, x + i);
int r1 = max(1, y - i);
int r2 = min(m, y + i);
Line t1(-1, i+x+y);
all += t1.Count(l1, l2, r1, r2);
Line t2(1, i-x+y);
all += t2.Count(l1, l2, r1, r2);
Line t3(-1, -i+x+y);
all += t3.Count(l1, l2, r1, r2);
Line t4(1, -i-x+y);
all += t4.Count(l1, l2, r1, r2);
// printf("%d ", all);
if(n - x >= i) all --;
if(y > i) all --;
if(m - y >= i) all --;
// printf("%d %d\n", i, all);
if(all != mp[i])
return false;
}
std::printf("%d %d\n%d %d\n", n, m, x, y);
return true;
}
int main() {
int t;
while(~scanf("%d", &t)) {
memset(mp, 0, sizeof(mp));
maxNum = -1;
for(int i = 0; i < t; ++i) {
scanf("%d", &A[i]);
mp[A[i]] ++;
maxNum = max(maxNum, A[i]);
}
bool flag = true; int X;
for(int i = 0; ; ++i) {
int id = i; int num = mp[i];
if(id == 0) {
flag &= num == 1;
} else {
flag &= num == 4*i;
}
if(flag == false) {
X = i;
break;
}
}
// for(int i = 0; i < t; ++i) printf("%d ", mp[i]); printf("\n");
// printf("%d\n", X);
if(X == 0) {
printf("-1\n");
continue;
}
flag = false;
for(int i = 1; i <= sqrt(t) && !flag; ++i) {
if(t % i == 0) {
int n = i; int m = t / i;
flag = Test(n, m, X);
if(!flag) {
flag = Test(m, n, X);
}
}
}
if(!flag) {
printf("-1\n");
}
}
return 0;
}
