正文
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个点
暴力搜索代码
#include<stdio.h>
#define SIZE 1005
typedef struct POINT {
int x;
int y;
} point;
int isSquare(int a, int b, int c, int d);
point p[SIZE];
int main() {
int n, result;
int i, j, k, x;
scanf("%d", &n);
while(n != ) {
result = ;
for(i=; i<=n; i++)
scanf("%d %d", &p[i].x, &p[i].y);
for(i=; i<=n; i++) {
for(j=i+; j<=n; j++) {
for(k=j+; k<=n; k++) {
for(x=k+; x<=n; x++) {
if(isSquare(i, j, k, x))
result++;
}
}
}
}
printf("%d\n", result);
scanf("%d", &n);
}
} int isSquare(int a, int b, int c, int d) {
int s[];
int num1 = , num2 = ;
int side1 = -, side2 = -;
int i;
s[] = (p[a].x - p[b].x)*(p[a].x - p[b].x) + (p[a].y - p[b].y)*(p[a].y - p[b].y);
s[] = (p[a].x - p[c].x)*(p[a].x - p[c].x) + (p[a].y - p[c].y)*(p[a].y - p[c].y);
s[] = (p[a].x - p[d].x)*(p[a].x - p[d].x) + (p[a].y - p[d].y)*(p[a].y - p[d].y);
s[] = (p[b].x - p[c].x)*(p[b].x - p[c].x) + (p[b].y - p[c].y)*(p[b].y - p[c].y);
s[] = (p[b].x - p[d].x)*(p[b].x - p[d].x) + (p[b].y - p[d].y)*(p[b].y - p[d].y);
s[] = (p[c].x - p[d].x)*(p[c].x - p[d].x) + (p[c].y - p[d].y)*(p[c].y - p[d].y);
for(i=; i<=; i++) {
if(i == ) {
side1 = s[i];
}
else if(s[i] != side1) {
if(side2 == -)
side2 = s[i];
else if(s[i] == side2)
num2++;
else
break;
}
else if(s[i] == side1)
num1++;
}
if((num1== && num2==) || (num1== && num2 == ))
return ;
else
return ;
}
使用堆排序+二分查找代码
#include<stdio.h>
#define SIZE 1005
typedef struct POiNT {
int x;
int y;
} point;
int cmp(point pa, point pb);
void heapSort(int n);
int binarySearch(int low, int high, point key);
void shiftDown(int i, int n);
void swap(int i, int j);
point p[SIZE];
int main() {
int n, result;
int i, j, k, x;
point pa, pb;
scanf("%d", &n);
while(n != ) {
result = ;
for(i=; i<=n; i++)
scanf("%d %d", &p[i].x, &p[i].y);
heapSort(n);
for(i=; i<=n; i++)
printf("%d %d\n", p[i].x, p[i].y); for(i=; i<=n; i++) {
for(j=i+; j<=n; j++) {
pa.x = p[i].x - (p[j].y - p[i].y);
pa.y = p[i].y + (p[j].x - p[i].x);
pb.x = pa.x + (p[j].x - p[i].x);
pb.y = pa.y + (p[j].y - p[i].y);
if(binarySearch(, n, pa) && binarySearch(, n, pb))
result++;
}
}
printf("%d\n", result/);
scanf("%d", &n);
}
}
int binarySearch(int low, int high, point key) {
int mid = (low + high)/;
if(low > high)
return ;
if(cmp(p[mid], key) == )
return ;
else if(cmp(p[mid], key) == )
return binarySearch(low, mid-, key);
else
return binarySearch(mid+, high, key);
}
void heapSort(int n) {
int i = n/;
for(; i>; --i)
shiftDown(i, n);
for(i=n; i>;) {
swap(, i);
shiftDown(, --i);
}
}
void shiftDown(int i, int n) {
int j = *i;
for(; j<=n; j=*i) {
if(j < n && cmp(p[j], p[j+]) == -)
j = j + ;
if(cmp(p[i], p[j]) == -) {
swap(i, j);
i = j;
} else
break;
}
}
void swap(int i, int j) {
point temp = p[i];
p[i] = p[j];
p[j] = temp;
}
int cmp(point pa, point pb) {
if(pa.x > pb.x)
return ;
else if(pa.x == pb.x && pa.y > pb.y)
return ;
else if(pa.x == pb.x && pa.y == pb.y)
return ;
else
return -;
}
考虑象限的hash代码
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define SIZE 1013
typedef struct POiNT {
int x;
int y;
} point;
struct hashNode {
point poi;
struct hashNode *next;
};
int cmp(const void *a, const void *b );
void add(point key);
int find(point);
point p[SIZE];
struct hashNode hashTable[][SIZE];
int main() {
int n, result;
int i, j, k, x;
point pa, pb;
scanf("%d", &n);
while(n != ) {
result = ;
memset(hashTable, , sizeof(hashTable));
for(i=; i<=n; i++) {
scanf("%d %d", &p[i].x, &p[i].y);
add(p[i]);
}
qsort(p+, n, sizeof(p[]), cmp);
for(i=; i<=n; i++) {
for(j=i+; j<=n; j++) {
pa.x = p[i].x - (p[j].y - p[i].y);
pa.y = p[i].y + (p[j].x - p[i].x);
pb.x = pa.x + (p[j].x - p[i].x);
pb.y = pa.y + (p[j].y - p[i].y);
if(find(pa) && find(pb))
result++;
}
}
printf("%d\n", result/);
scanf("%d", &n);
}
}
void add(point key) {
int t, num;
struct hashNode *newNode;
if(key.x >= && key.y >= )
t = ;
else if(key.x >= && key.y < )
t = ;
else if(key.x < && key.y < )
t = ;
else
t = ;
num = (key.x*key.x + key.y*key.y)%SIZE;
newNode = (struct hashNode*)malloc(sizeof(struct hashNode));
newNode->poi = key;
newNode->next = hashTable[t][num].next;
hashTable[t][num].next = newNode;
}
int find(point key) {
int t, num;
struct hashNode *node;
if(key.x >= && key.y >= )
t = ;
else if(key.x >= && key.y < )
t = ;
else if(key.x < && key.y < )
t = ;
else
t = ;
num = (key.x*key.x + key.y*key.y)%SIZE;
node = hashTable[t][num].next;
while(node) {
if(node->poi.x == key.x && node->poi.y == key.y)
return ;
node = node->next;
}
return ;
}
int cmp(const void *a, const void *b )
{
point c = *(point*)a;
point d = *(point*)b; if(c.x == d.x)
return c.y - d.y;
else
return c.x - d.x;
}
