hdu 6055 : Regular polygon (2017 多校第二场 1011) 【计算几何】
2024-09-05 23:07:57
有个结论: 平面坐标系上,坐标为整数的情况下,n个点组成正n边形时,只可能组成正方形。
然后根据这个结论来做。
我是先把所有点按照 x为第一关键字,y为第二关键字 排序,然后枚举向量 (p[i]->p[j]) (j>i),只判断这个向量左侧可否存在两个点与它一起构成一个正方形。这样算的结果是,计数每个正方形时,它的靠右和靠下的两条边都会为ans贡献一个单位,所以最后ans要除以2。
#include<bits/stdc++.h>
using namespace std; int n;
int vis[][]; struct point
{
int x,y;
bool operator<(const point& rhs)const
{
return x<rhs.x || x==rhs.x&&y<rhs.y;
}
}p[]; int main()
{
while(~scanf("%d",&n))
{
memset(vis,,sizeof(vis));
int ans=;
for(int i=;i<n;i++)
{
scanf("%d%d",&p[i].x,&p[i].y);
p[i].x+=,p[i].y+=;
vis[p[i].x][p[i].y]=;
}
sort(p,p+n);
for(int i=;i<n;i++)
for(int j=i+;j<n;j++)
{
point a=p[i],b=p[j];
int dx=b.x-a.x;
int dy=b.y-a.y;
point c,d;
c.x=a.x-dy,c.y=a.y+dx;
d.x=b.x-dy,d.y=b.y+dx;
if(vis[c.x][c.y]&&vis[d.x][d.y]) ans++;
}
printf("%d\n",ans/);
}
}
最新文章
- 1.注册或登录页面设计:UILabel,UIButton,UITextField
- [OpenCV] 1、读取图片
- 事务的四个特性-ACID
- Linux下挂载NTFS格式的U盘或硬盘
- JS手册目录
- Python模块学习
- .NET垃圾回收 – 非托管资源
- 非常详细GC学习笔记
- 传智博客(JavaWeb方面的所有知识)听课记录(经典)
- awesome awesomeness
- 【Android - MD】之TabLayout的使用
- Redis 入门之编译安装
- oracle解锁表
- TCP的三次握手和四次挥手(转)
- gRPC官方快速上手学习笔记(c#版)
- Erlang epmd官方文档中文翻译
- 升级ssh到OpenSSH_7.5p1
- Android 设置app 启动
- golang查看channel缓冲区的长度
- Ubuntu 18.04上安装R及Rstudio