首页 > 代码库 > Poj2002 Squares
Poj2002 Squares
题意描述：有一堆平面散点集，任取四个点，求能组成正方形的不同组合方式有多少。相同的四个点，不同顺序构成的正方形视为同一正方形。
思路变迁：
1、最简单的方法，直接暴力搜索，即依次取四个顶点，根据其坐标判断是否能组成正方形。组成正方形的条件是四个顶点可组成的六条边里面，有四条相等，剩下两条相等。当然由于其时间复杂度为O(n^4)，所以提交结果为TLE
2、考虑降低时间复杂度。如任取三个顶点，根据组成正方形的条件计算得到第四个顶点，判断其是否在点的集合内，其复杂度为O(n^3)。或者任取两个顶点，根据组成正方形的条件计算出另外两个顶点，再判断其是否在点的集合内，其复杂度为O(n^2)。
3、不论是任取两个顶点还是任取三个顶点，其关键一步都是判断计算得到的新的点，是否在点的集合内，基本方法有对点排序再二分查找，或者是使用hash表。我的设计是考虑点所处象限的二维hash表。根据这道题的提交结果来看，所用时间上，堆排序优于快排
4、对于任选两个顶点时，可能存在三种不同的正方形。但是在对所有顶点排序后，如若按序来去顶点，则可发现我们只需始终计算一个方向的即可，且计算结果中同一个正方形重复了两次，所以最终结果除以二。如若不排序直接任取两个的顶点的话，始终按一个方向计算，可以发现每个正方形的四条边，每一条边都会贡献一次得到的正方形的个数，所以最终结果需要除以四
5、在使用hash表后时间复杂度达到最优，即O(nlgn) + hash表平均冲突*n(n-1)/2，所以本问题的进一步优化，取决于怎么更大程度的降低hash表的冲突？考虑位运算，来存储所有的点，但需要空间太大，因为共有40000*40000个点
暴力搜索代码
1 #include<stdio.h> 2 #define SIZE 1005 3 typedef struct POINT { 4 int x; 5 int y; 6 } point; 7 int isSquare(int a, int b, int c, int d); 8 point p[SIZE]; 9 int main() {10 int n, result;11 int i, j, k, x;12 scanf("%d", &n);13 while(n != 0) {14 result = 0;15 for(i=1; i<=n; i++)16 scanf("%d %d", &p[i].x, &p[i].y);17 for(i=1; i<=n; i++) {18 for(j=i+1; j<=n; j++) {19 for(k=j+1; k<=n; k++) {20 for(x=k+1; x<=n; x++) {21 if(isSquare(i, j, k, x))22 result++;23 }24 }25 }26 }27 printf("%d\n", result);28 scanf("%d", &n);29 }30 }31 32 int isSquare(int a, int b, int c, int d) {33 int s[6];34 int num1 = 1, num2 = 1;35 int side1 = -1, side2 = -1;36 int i;37 s[0] = (p[a].x - p[b].x)*(p[a].x - p[b].x) + (p[a].y - p[b].y)*(p[a].y - p[b].y);38 s[1] = (p[a].x - p[c].x)*(p[a].x - p[c].x) + (p[a].y - p[c].y)*(p[a].y - p[c].y);39 s[2] = (p[a].x - p[d].x)*(p[a].x - p[d].x) + (p[a].y - p[d].y)*(p[a].y - p[d].y);40 s[3] = (p[b].x - p[c].x)*(p[b].x - p[c].x) + (p[b].y - p[c].y)*(p[b].y - p[c].y);41 s[4] = (p[b].x - p[d].x)*(p[b].x - p[d].x) + (p[b].y - p[d].y)*(p[b].y - p[d].y);42 s[5] = (p[c].x - p[d].x)*(p[c].x - p[d].x) + (p[c].y - p[d].y)*(p[c].y - p[d].y);43 for(i=0; i<=5; i++) {44 if(i == 0) {45 side1 = s[i];46 }47 else if(s[i] != side1) {48 if(side2 == -1)49 side2 = s[i];50 else if(s[i] == side2)51 num2++;52 else53 break;54 }55 else if(s[i] == side1)56 num1++;57 }58 if((num1==2 && num2==4) || (num1==4 && num2 == 2))59 return 1;60 else61 return 0;62 }
使用堆排序+二分查找代码
1 #include<stdio.h> 2 #define SIZE 1005 3 typedef struct POiNT { 4 int x; 5 int y; 6 } point; 7 int cmp(point pa, point pb); 8 void heapSort(int n); 9 int binarySearch(int low, int high, point key);10 void shiftDown(int i, int n);11 void swap(int i, int j);12 point p[SIZE];13 int main() {14 int n, result;15 int i, j, k, x;16 point pa, pb;17 scanf("%d", &n);18 while(n != 0) {19 result = 0;20 for(i=1; i<=n; i++)21 scanf("%d %d", &p[i].x, &p[i].y);22 heapSort(n);23 for(i=1; i<=n; i++)24 printf("%d %d\n", p[i].x, p[i].y);25 26 for(i=1; i<=n; i++) {27 for(j=i+1; j<=n; j++) {28 pa.x = p[i].x - (p[j].y - p[i].y);29 pa.y = p[i].y + (p[j].x - p[i].x);30 pb.x = pa.x + (p[j].x - p[i].x);31 pb.y = pa.y + (p[j].y - p[i].y);32 if(binarySearch(1, n, pa) && binarySearch(1, n, pb))33 result++;34 }35 }36 printf("%d\n", result/2);37 scanf("%d", &n);38 }39 }40 int binarySearch(int low, int high, point key) {41 int mid = (low + high)/2;42 if(low > high)43 return 0;44 if(cmp(p[mid], key) == 0)45 return 1;46 else if(cmp(p[mid], key) == 1)47 return binarySearch(low, mid-1, key);48 else49 return binarySearch(mid+1, high, key);50 }51 void heapSort(int n) {52 int i = n/2;53 for(; i>0; --i)54 shiftDown(i, n);55 for(i=n; i>1;) {56 swap(1, i);57 shiftDown(1, --i);58 }59 }60 void shiftDown(int i, int n) {61 int j = 2*i;62 for(; j<=n; j=2*i) {63 if(j < n && cmp(p[j], p[j+1]) == -1)64 j = j + 1;65 if(cmp(p[i], p[j]) == -1) {66 swap(i, j);67 i = j;68 } else69 break;70 }71 }72 void swap(int i, int j) {73 point temp = p[i];74 p[i] = p[j];75 p[j] = temp;76 }77 int cmp(point pa, point pb) {78 if(pa.x > pb.x)79 return 1;80 else if(pa.x == pb.x && pa.y > pb.y)81 return 1;82 else if(pa.x == pb.x && pa.y == pb.y)83 return 0;84 else85 return -1;86 }
考虑象限的hash代码
1 #include<stdio.h> 2 #include<stdlib.h> 3 #include<string.h> 4 #define SIZE 1013 5 typedef struct POiNT { 6 int x; 7 int y; 8 } point; 9 struct hashNode {10 point poi;11 struct hashNode *next;12 };13 int cmp(const void *a, const void *b );14 void add(point key);15 int find(point);16 point p[SIZE];17 struct hashNode hashTable[5][SIZE];18 int main() {19 int n, result;20 int i, j, k, x;21 point pa, pb;22 scanf("%d", &n);23 while(n != 0) {24 result = 0;25 memset(hashTable, 0, sizeof(hashTable));26 for(i=1; i<=n; i++) {27 scanf("%d %d", &p[i].x, &p[i].y);28 add(p[i]);29 }30 qsort(p+1, n, sizeof(p[0]), cmp);31 for(i=1; i<=n; i++) {32 for(j=i+1; j<=n; j++) {33 pa.x = p[i].x - (p[j].y - p[i].y);34 pa.y = p[i].y + (p[j].x - p[i].x);35 pb.x = pa.x + (p[j].x - p[i].x);36 pb.y = pa.y + (p[j].y - p[i].y);37 if(find(pa) && find(pb))38 result++;39 }40 }41 printf("%d\n", result/2);42 scanf("%d", &n);43 }44 }45 void add(point key) {46 int t, num;47 struct hashNode *newNode;48 if(key.x >= 0 && key.y >= 0)49 t = 1;50 else if(key.x >= 0 && key.y < 0)51 t = 2;52 else if(key.x < 0 && key.y < 0)53 t = 3;54 else55 t = 4;56 num = (key.x*key.x + key.y*key.y)%SIZE;57 newNode = (struct hashNode*)malloc(sizeof(struct hashNode));58 newNode->poi = key;59 newNode->next = hashTable[t][num].next;60 hashTable[t][num].next = newNode;61 }62 int find(point key) {63 int t, num;64 struct hashNode *node;65 if(key.x >= 0 && key.y >= 0)66 t = 1;67 else if(key.x >= 0 && key.y < 0)68 t = 2;69 else if(key.x < 0 && key.y < 0)70 t = 3;71 else72 t = 4;73 num = (key.x*key.x + key.y*key.y)%SIZE;74 node = hashTable[t][num].next;75 while(node) {76 if(node->poi.x == key.x && node->poi.y == key.y)77 return 1;78 node = node->next;79 }80 return 0;81 }82 int cmp(const void *a, const void *b )83 {84 point c = *(point*)a;85 point d = *(point*)b;86 87 if(c.x == d.x)88 return c.y - d.y;89 else90 return c.x - d.x;91 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。