首页 > 代码库 > hdu6055 Regular polygon 脑洞几何 给定n个坐标(x,y)。x,y都是整数,求有多少个正多边形。因为点都是整数点,所以只可能是正四边形。

hdu6055 Regular polygon 脑洞几何 给定n个坐标(x,y)。x,y都是整数,求有多少个正多边形。因为点都是整数点,所以只可能是正四边形。

/**
题目:hdu6055 Regular polygon
链接:http://acm.hdu.edu.cn/showproblem.php?pid=6055
题意:给定n个坐标(x,y)。x,y都是整数,求有多少个正多边形。因为点都是整数点,所以只可能是正四边形。
思路:
(x1,y2)(x2,y2)=》(x,y) = (x2-x1,y2-y1)
向量(x,y)逆时针旋转90度:(-y,x);那么可以得到垂直(x,y)的向量,并通过(x2,y2)获得以(x2,y2)为起点的向量终点(x2+(-y),y2+x);
然后继续旋转90度,(-x,-y);那么得到以(x2+(-y),y2+x)为起点的向量终点(x2+(-y)+(-x),y2+x+(-y));如果求出来的这两个点都存在,
那么这四个点可以构成正四边形。由于一个正四边形四条边,所以每个正四边形算了四次,最后/4即可。

*/

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<map>
#include<vector>
#include<queue>
#include<cstring>
#include<cmath>
using namespace std;
typedef pair<int,int> P;
typedef long long LL;
const int N = 505;
const int mod = 1e9+7;
const int INF = 0x3f3f3f3f;
int f[202][202];
struct node
{
    int x, y;
}t[N];
void rotate(int &vx,int &vy)
{
    int t = -vy;
    vy = vx;
    vx = t;
}
int solve(int i,int j)
{
    int vx = t[j].x-t[i].x, vy = t[j].y-t[i].y;
    rotate(vx,vy);
    int x = t[j].x+vx, y = t[j].y+vy;
    rotate(vx,vy);
    int xx = x+vx, yy = y+vy;
    if(x>200||y>200||xx>200||yy>200||x<0||y<0||xx<0||yy<0) return 0;
    return f[x][y]&&f[xx][yy];
}
int main(void)
{
    int n;
    while(scanf("%d",&n)==1)
    {
        memset(f, 0, sizeof f);
        for(int i = 1; i <= n; i++){
            scanf("%d%d",&t[i].x,&t[i].y);
            t[i].x+=100, t[i].y+=100;
            f[t[i].x][t[i].y] = 1;
        }
        int ans = 0;
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                if(i==j) continue;
                ans += solve(i,j);
            }
        }
        printf("%d\n",ans/4);
    }
    return 0;
}

 

hdu6055 Regular polygon 脑洞几何 给定n个坐标(x,y)。x,y都是整数,求有多少个正多边形。因为点都是整数点,所以只可能是正四边形。