hdu6055 Regular polygon【思维+几何基础】

sanyue科研 lv.1

发布时间：2022-11-28 18:46:43 112

相关标签： # php

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6055
题意：给你n个坐标为整数的点，让你求有有多少个正多边形
解析：首先这个正多边形一定是正四边形，因为点是整点，接下来需要判断有几个，那么枚举两个点，然后去找这条线段构成的正方形是否存在，找正方形，用坐标旋转即可（90度很特殊，算起来很快）

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;
typedef long long LL;
struct point
{
    int x,y;
}a[505];
int vis[1000][1000];
bool shun(point p0,point p1)
{
    int x1 = p1.y-p0.y+p1.x;
    int y1 = p0.x-p1.x+p1.y;
    int x2 = p1.y-p0.y+p0.x;
    int y2 = p0.x-p1.x+p0.y;
    return vis[x1+500][y1+500]&&vis[x2+500][y2+500];
}
bool ni(point p0,point p1)
{
    int x1 = p0.y-p1.y+p0.x;
    int y1 = p1.x-p0.x+p0.y;
    int x2 = p0.y-p1.y+p1.x;
    int y2 = p1.x-p0.x+p1.y;
    return vis[x1+500][y1+500]&&vis[x2+500][y2+500];
}
int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        memset(vis,0,sizeof(vis));
        for(int i=0;i<n;i++)
        {
            scanf("%d %d",&a[i].x,&a[i].y);
            vis[a[i].x+500][a[i].y+500] = 1;
        }
        int ans = 0;
        for(int i=0;i<n;i++)
        {
            for(int j=i+1;j<n;j++)
            {
                if(shun(a[i],a[j]))
                    ans++;
                if(ni(a[i],a[j]))
                    ans++;
            }
        }
        printf("%d\n",ans/4);
    }
    return 0;
}
/*
9
0 0
0 1
0 2
1 0
1 1
1 2
2 0
2 1
2 2
*/

文章来源： https://blog.51cto.com/u_11435021/5880254

特别声明：以上内容（图片及文字）均为互联网收集或者用户上传发布，本站仅提供信息存储服务！如有侵权或有涉及法律问题请联系我们。