Regular polygon

time limit per test 1 second memory limit per test 256 megabytes
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.

传送门:HDU6055

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

1
2
3
4
5
6
7
8
9
10
11
12
4
0 0
0 1
1 0
1 1
6
0 0
0 1
1 0
1 1
2 0
2 1

Sample Output

1
2
1
2

题解

题意:给一些二维整点 能构成多少个不同的正多边形
结论:只能构成正四边形
先按x从小到大排 再按y从小到大排(保证对角线两点的有序性)
然后枚举对角线的两点 O(1)公式找到另外两点:
int x3=y1-y2+x1;int y3=x2-x1+y1;
int x4=y1-y2+x2;int y4=x2-x1+y2;
最后因为一个正方形这样的对角线有两条 所以要除以2
更一般的:假设对图片上任意点(x,y),绕一个坐标点(rx0,ry0)逆时针旋转a角度后的新的坐标设为(x0, y0),有公式:
x0= (x - rx0)×cos(a) - (y - ry0)×sin(a) + rx0 ;
y0= (x - rx0)×sin(a) + (y - ry0)×cos(a) + ry0 ;

AC code:(不包含输入类)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
import java.io.*;  
import java.util.*;
public class Main {

public static void main(String[] args) {
FastScanner sc=new FastScanner();
PrintWriter pw=new PrintWriter(System.out);
while(sc.hasNext()){
int n=sc.nextInt();
HashSet<Integer>[]set=new HashSet[205];
Node[]node=new Node[n];
for(int i=0;i<205;i++)set[i]=new HashSet<Integer>();
for(int i=0;i<n;i++){
int x=sc.nextInt();
int y=sc.nextInt();
node[i]=new Node(x,y);
set[y+100].add(x);
}
int count=0;
Arrays.sort(node);
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
int x1=node[i].x;int y1=node[i].y;
int x2=node[j].x;int y2=node[j].y;
int x3=y1-y2+x1;int y3=x2-x1+y1;
int x4=y1-y2+x2;int y4=x2-x1+y2;
if(y3>=-100&&y3<=100&&y4>=-100&&y4<=100){
int num3=y3+100;
int num4=y4+100;
if(set[num3].contains(x3)&&set[num4].contains(x4))count++;
}
}
}
pw.println(count/2);
pw.flush();
}

}
}
class Node implements Comparable<Node>{
int x;
int y;
Node(int a,int b){
x=a;
y=b;
}
@Override
public int compareTo(Node o) {
if(this.x<o.x)return -1;
if(this.x>o.x)return 1;
if(this.y<o.y)return -1;
if(this.y>o.y)return 1;
return 0;
}
}