[COGS2426][HZOI 2016]几何

题目大意：

给定平面坐标系内\(n\)个整点，求这些整点能构成的正多边形的边数的最大值。

思路：

一个基本结论：平面直角坐标系内能够形成的正多边形一定是正方形。

因此枚举两个点就可以推出另外两个点，判断这两个点是否在给定的点集中即可。

时间复杂度\(\mathcal O(n^2\log n)\)。

源代码：

#include<set>

#include<cstdio>

#include<cctype>

inline int getint() {

	register char ch;

	register bool neg=false;

	while(!isdigit(ch=getchar())) neg=ch=='-';

	register int x=ch^'0';

	while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');

	return neg?-x:x;

}

const int N=1001;

struct Point {

	int x,y;

	bool operator < (const Point &rhs) const {

		return x==rhs.x?y<rhs.y:x<rhs.x;

	}

};

Point p[N];

std::set<Point> set;

int main() {

	freopen("geometry.in","r",stdin);

	freopen("geometry.out","w",stdout);

	for(register int T=getint();T;T--) {

		const int n=getint();

		for(register int i=1;i<=n;i++) {

			p[i].x=getint();

			p[i].y=getint();

			set.insert(p[i]);

		}

		for(register int i=1;i<=n;i++) {

			const Point &a=p[i];

			for(register int j=1;j<=n;j++) {

				if(i==j) continue;

				const Point &b=p[j];

				const int d1=a.y-b.y,d2=b.x-a.x;

				const Point &c=(Point){a.x+d1,a.y+d2};

				const Point &d=(Point){b.x+d1,b.y+d2};

				if(set.count(c)&&set.count(d)) {

					puts("4");

					goto Next;

				}

			}

		}

		puts("-1");

		Next:;

		set.clear();

	}

	return 0;

}