| Time Limit: 3500MS | Memory Limit: 65536K | |
| Total Submissions: 16615 | Accepted: 6320 |
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
4 1 0 0 1 1 1 0 0 9 0 0 1 0 2 0 0 2 1 2 2 2 0 1 1 1 2 1 4 -2 5 3 7 0 0 5 2 0
Sample Output
1 6 1
给出n个点，求出有可以组成多少个正方形？
枚举对角的两个点，然后求解出其他的两个点，将这两个点带入到n个点中查找，可以hash 或 二分。
已知对角线的点 (x1,y1) (x3,y3) 求出中点( (x1+x3)/2 , (y1+y3)/2 ) ->（X,Y） 用对角线的一个点减去中点得到(x,y)，那么其他的两个点就是( x1-Y,y1+X ) （x1+Y,y1-X）
#include#include #include #include #include using namespace std ; #define eqs 1e-9 struct node{ double x , y ; }p[1100] ; bool cmp(node a,node b) { return ( a.x < b.x || ( a.x == b.x && a.y < b.y ) ) ; } bool judge(double x,double y,int n) { int low = 0 , mid , high = n-1 ; while( low <= high ) { mid = (low + high) / 2 ; if( fabs(p[mid].x-x) < eqs && fabs(p[mid].y-y) < eqs ) return true ; else if( p[mid].x-x > eqs || ( fabs(p[mid].x-x) < eqs && p[mid].y-y > eqs ) ) high = mid - 1 ; else low = mid + 1 ; } return false ; } int main() { int n , i , j , num ; double x , y , xx , yy ; while( scanf("%d", &n) && n ) { num = 0 ; for(i = 0 ; i < n ; i++) { scanf("%lf %lf", &p[i].x, &p[i].y) ; } sort(p,p+n,cmp) ; for(i = 0 ; i < n ; i++) { for(j = i+1 ; j < n ; j++) { if( i == j ) continue ; x = (p[i].x+p[j].x)/2 ; y = (p[i].y+p[j].y)/2 ; xx = p[i].x - x ; yy = p[i].y - y ; if( judge(x+yy,y-xx,n) && judge(x-yy,y+xx,n) ) { //printf("(%.1lf,%.1lf) (%.1lf,%.1lf) (%.1lf,%.1lf) (%.1lf,%.1lf)\n", p[i].x, p[i].y , p[j].x, p[j].y,x+yy,y-xx,x-yy,y+xx ) ; num++ ; } } } printf("%d\n", num/2) ; } return 0; }