【题目描述】 农民约翰打算建一个新的矩形谷仓。但是,矩形谷仓的 4 个角落不能在落在软土路基上,只能落在一些固定点上。现在,他已经找到地面上有 N（4 <= N <= 1,000）个点,角落只可以落在这些点上。他想知道依次每加多一个点，可以建立新谷仓的方法数量,请你帮助他找到答案。 【输入格式】 第 1 行一个整数N 第 2 行至 N +1 行每行有两个被空格分隔的整数的 x，y,作为一个点的坐标。所有的 x,y 都不会超过 16,000。所有点都是不同的。 【输出格式】 共 N 行，每行表示当前可以建立的新的谷仓的数目。 【样例输入】 8 1 2 1 -2 2 1 2 -1 -1 2 -1 -2 -2 1 -2 -1 【样例输出】 0 0 0 0 0 1 3 6 【分析】 判断一个图形是不是矩形，一种直接的思路是枚举三个点，再判断第四个点，但是这种方法显然不可行。转换一种思路，保存每条对角线的长度和两个端点的坐标（如果两条对角线长度相等，中点重合，则其一定是一个矩形）即可。
const inf=1123357; step=13131; var i,j:longint; n,x0,y0,len,p,c,ans:int64; x,y,xx,yy,ll,h,num:array[0..inf]of int64; begin fillchar(h,sizeof(h),0); fillchar(xx,sizeof(xx),0); fillchar(yy,sizeof(yy),0); fillchar(ll,sizeof(ll),0); fillchar(num,sizeof(num),0); c:=0; ans:=0; readln(n); for i:=1 to n do begin readln(x[i],y[i]); for j:=1 to i-1 do begin x0:=x[i]+x[j]; y0:=y[i]+y[j]; len:=sqr(x[i]-x[j])+sqr(y[i]-y[j]); p:=(abs(x0*1343+y0*3217+len*1321)) mod inf; while (h[p]<>0)and((x0<>xx[h[p]])or(y0<>yy[h[p]])or(len<>ll[h[p]])) do p:=(p+step) mod inf; if h[p]=0 then begin inc(c); h[p]:=c; xx[c]:=x0; yy[c]:=y0; ll[c]:=len; num[h[p]]:=num[h[p]]+1; end else begin ans:=ans+num[h[p]]; inc(num[h[p]]); end; end; writeln(ans); end; end.转载于:https://www.cnblogs.com/JRX2015U43/p/6533544.html
