poj2002Squares(n个点求正方形个数) -电脑资料

    SquaresTime Limit:3500MSMemory Limit:65536KTotal Submissions:16615Accepted: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

41 00 11 10 090 01 02 00 21 22 20 11 12 14-2 53 70 05 20

    Sample Output

161

    给出n个点，求出有可以组成多少个正方形？

    枚举对角的两个点，然后求解出其他的两个点，将这两个点带入到n个点中查找，可以hash 或 二分，

poj2002Squares(n个点求正方形个数)

，

电脑资料

《poj2002Squares(n个点求正方形个数)》(https://www.unjs.com)。

    已知对角线的点 (x1,y1) (x3,y3) 求出中点( (x1+x3)/2 , (y1+y3)/2 ) ->（X,Y） 用对角线的一个点减去中点得到(x,y)，那么其他的两个点就是( x1-Y,y1+X ) （x1+Y,y1-X）

#include<cstdio>#include<cstring>#include #include<cmath>#include<vector>using namespace std ;#define eqs 1e-9struct 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;}