Squares
| Time Limit: 3500MS | Memory Limit: 65536K | |
| Total Submissions: 18493 | Accepted: 7124 |
Description
A square is a 4-sided polygon whose sides have equal length and adjacent sides form 90-degree angles. It is also a polygon such that rotating about its centre by 90 degrees gives the same polygon. It is not the only polygon with the latter property, however, as a regular octagon also has this property. So we all know what a square looks like, but can we find all possible squares that can be formed from a set of stars in a night sky? To make the problem easier, we will assume that the night sky is a 2-dimensional plane, and each star is specified by its x and y coordinates.
Input
The input consists of a number of test cases. Each test case starts with the integer n (1 <= n <= 1000) indicating the number of points to follow. Each of the next n lines specify the x and y coordinates (two integers) of each point. You may assume that the points are distinct and the magnitudes of the coordinates are less than 20000. The input is terminated when n = 0.
Output
For each test case, print on a line the number of squares one can form from the given stars.
Sample Input
41 00 11 10 090 01 02 00 21 22 20 11 12 14-2 53 70 05 20
Sample Output
161 题意：平面上有n个点,问n个点能够组成多少个正方形. 初看很简单,就是枚举每两个点去找另外两个点..然后我马上遇到了难题,我准备用bool去存点，结果试了一下 40000*40000直接爆掉了..然后正方形的其余两个点不会求..因为这题都是整形，用斜率求肯定 会出问题（平时做几何体，最好不要用斜率，因为会有正无穷）。然后竟然有公式！！用全等三角形可以证明。。。我等膜拜。。然后就是不能用bool只能用hash了。。hash又是一个好的借鉴。。链式前向星 存的。。
#include#include #include #include #include using namespace std;const int maxn = 1005;const int H = 10000;struct Point{ int x,y;} p[maxn],C,D;///************************hash模板 int Hash[H],cur;void initHash(){ memset(Hash,-1,sizeof(Hash)); cur =0;}struct Node{ int x,y; int next;} node[maxn];void InsertHash(int x,int y){ int h=(x*x + y*y) % H; node[cur].x=x; node[cur].y=y; node[cur].next=Hash[h]; Hash[h]=cur++;}bool SearchHash(int x,int y){ int h=(x*x + y*y) % H; int next=Hash[h]; while(next != -1) { if(node[next].x == x && node[next].y == y) return true; next = node[next].next; } return false;}/*******************************////已知正方形 a,b 两点求解另外两点的 c,d的坐标(要分两种情况)void solve1(Point a,Point b,Point& c,Point& d) ///情况1{ c.x = a.x + (a.y-b.y); c.y = a.y - (a.x-b.x); d.x = b.x + (a.y-b.y); d.y = b.y - (a.x-b.x);}void solve2(Point a,Point b,Point& c,Point& d) ///情况2(反过来){ c.x = a.x - (a.y-b.y); c.y = a.y + (a.x-b.x); d.x = b.x - (a.y-b.y); d.y = b.y + (a.x-b.x);}int main(){ int n; while(scanf("%d",&n)!=EOF&&n) { initHash(); for(int i=0; i