首页 > 代码库 > poj2002--Squares(n个点求正方形个数)

poj2002--Squares(n个点求正方形个数)

2024-08-07 07:53:51   222人阅读

Squares
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

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 或 二分。

已知对角线的点 (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 <algorithm>#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;}


 

 

poj2002--Squares(n个点求正方形个数)


联系
我们