首先如果有答案的话,那我们一定能旋转到
1 2 3 4 5 6 7
| ------- |\ | | |0\| | |-----| | | | | | | -------
|
这样的位置。
那么我们设离左上角的距离 $a=x-1+y-1$,右下角的 $b=n-x+m-y$。
$b$ 就是最大的数字,$x$ 就是不满足 $cnt_i=4i$ 的第一个 $i$(显然)。
然后我们爆枚 $n$,算出 $m$,推出 $y$,然后检查一下就行了。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38
| #include <iostream> #include <cstring> #include <cstdio> using namespace std; int T, a[1000005], cnt[1000005], mx, aa, bb, d[1000005], n, m, xx, yy; bool chk(int q){ n = q; m = T / n; yy = n + m - xx - mx; memset(d, 0, sizeof(d)); for(int i=1; i<=n; i++) for(int j=1; j<=m; j++){ int t=abs(i-xx)+abs(j-yy); d[t]++; } for(int i=0; i<T; i++) if(d[i]!=cnt[i]) return false; return true; } int main(){ cin>>T; for(int i=1; i<=T; i++){ scanf("%d", &a[i]); cnt[a[i]]++; mx = max(mx, a[i]); } for(xx=1; xx<T; xx++) if(cnt[xx]<xx*4) break; for(int i=1; i<=T; i++) if(T%i==0 && chk(i)){ cout<<n<<" "<<m<<endl<<xx<<" "<<yy<<endl; return 0; } cout<<"-1\n"; return 0; }
|