HDU 6055 Regular polygon （找正方形）

HDU 6055 Regular polygon （找正方形）

Description

On a two-dimensional plane, give you n integer points. Your task is to figure out how many different regular polygon these points can make.

Input

The input file consists of several test cases. Each case the first line is a numbers N (N <= 500). The next N lines ,each line contain two number Xi and Yi(-100 <= xi,yi <= 100), means the points’ position.(the data assures no two points share the same position.)

Output

For each case, output a number means how many different regular polygon these points can make.

Sample Input

40 00 11 01 160 00 11 01 12 02 1

Sample Output

12

题意

给出平面内 n 个点，问其中四个点组成正方形总共有多少种情况。

思路

因为 n≤500

寻找正方形，那么只需要知道其中相对的两个点便可以算出另外两个点咯！

所以我们只需要枚举其中两个点，然后计算出另外两个点的坐标，如果这两个点出现过则找到正方形，否则未找到。

在判断点是否出现过我们可以采用二分或者哈希等方法。

AC 代码

#include #include #include #include #include #includeusing namespace std ;#define eps 1e-7struct node{ double x,y;} p[510];int n;bool cmp(node a,node b){ if(a.x==b.x) return a.yeps||(fabs(p[mid].x-x)eps)) high=mid-1; else low=mid+1; } return false;}int main(){ ios::sync_with_stdio(false); while(cin>>n) { int ans=0; for(int i=0; i>p[i].x>>p[i].y; sort(p,p+n,cmp); for(int i=0; i

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。