题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=6055
题意: 给出 n 组坐标 x, y, 输出其中的正多边形个数 . 其中 x, y 均为整数.
思路: x, y 为整数, 所以只存在正方形, 不会有其他正多边形 . 那么只需要枚举正方形的对角线即可 .
代码:
1 #include <iostream> 2 #include <stdio.h> 3 #include <string.h> 4 #include <algorithm> 5 #define ll long long 6 using namespace std; 7 8 const int MAXN = 1e3 + 10; 9 const int H = 1e4 + 7; 10 11 struct node{ 12 int x, y, next; 13 }gel[MAXN]; 14 15 ll ans; 16 int head[H]; 17 int indx, n; 18 int ptx[MAXN], pty[MAXN]; 19 20 void init(void){ 21 memset(head, -1, sizeof(head)); 22 indx = 0; 23 ans = 0; 24 } 25 26 void add(int x, int y){ 27 int h = (x * x + y * y) % H; 28 gel[indx].x = x; 29 gel[indx].y = y; 30 gel[indx].next = head[h]; 31 head[h] = indx++; 32 } 33 34 bool find(int x, int y){ 35 int h = (x * x + y * y) % H; 36 for(int i = head[h]; i != -1; i = gel[i].next){ 37 if(x == gel[i].x && y == gel[i].y) return true; 38 } 39 return false; 40 } 41 42 int main(void){ 43 while(~scanf("%d", &n)){ 44 init(); 45 for(int i = 0; i < n ; i++){ 46 scanf("%d%d", &ptx[i], &pty[i]); 47 add(ptx[i], pty[i]); 48 } 49 for(int i = 0; i < n; i++){ 50 for(int j = 0; j < n; j++){ 51 if(i == j) continue; 52 int x1 = ptx[i] - (pty[i] - pty[j]); 53 int y1 = pty[i] + (ptx[i] - ptx[j]); 54 int x2 = ptx[j] - (pty[i] - pty[j]); 55 int y2 = pty[j] + (ptx[i] - ptx[j]); 56 if(find(x1, y1) && find(x2, y2)) ans++; 57 } 58 } 59 printf("%lld ", ans >> 2); 60 } 61 return 0; 62 }