c语言正方形个数问题

Question

给定坐标。。。计算一共有多少个正方形？ 例如：（0,0）（0,1）（1,0）（1,1），有一个正方形。。。。求 解题思路啊。。。。。。。。。。。。>-<~~~ 关键是 思路思路 ~~~ 来人 ~
★实验任务

在一个二维平面上给定N个点（ 4 <= N <= 1000）Pi(xi,yi) ( |xi| <= 20000 ,|yi| <= 20000，不存在重复点),请问在这些点中能形成多少个正方形。

★数据输入

每个样例第一行输入一个整数N（ 4 <= N <= 1000）,接下来有N行每行输入两个整数xi,yi代表点的坐标。

★数据输出

输出一行：的正方形的个数

输入示例

4

1 0

0 1

1 1

0 0

输出示例

1

输入示例

9

0 0

1 0

2 0

0 2

1 2

2 2

0 1

1 1

2 1

输出示例

6

Answer 1

http://zhidao.baidu.com/question/72851978.html
真的是很复杂的题。希望我没有说错。
其实当n>=4时，还存在一些位置比较偏的正方形。
比如n=4时，（1，2）（2，4）（3，1）（4，3）四个点也是一个正方形。同时还有一个和它对称着的正方形。一条边斜着占1*2的空间。
n>4时，情况会更加复杂。

假设a*b是一条边占的空间为a个长b个宽。n=3时的正的正方形记为1*0和2*0，菱形记为1*1。n>3时，a*b和b*a表示形状对称的一些偏的正方形。
那么，正方形的种类：
第一组：1*0，2*0，…，(n-1)*0.
二：1*1,1*2,1*3,...,1*(n-2).
三：2*1,2*2,2*3,...,2*(n-3).
……
第n-2组:(n-3)*1,(n-3)*2.
第n-1组：(n-2)*1.
其中，a*b组中，存在的正方形个数为(n-a-b)^2.
总的正方形为：
1^2+2^2+3^2+...+(n-1)^2 ...1
+ 1^2+2^2+3^2+...+(n-2)^2 ...2
+ 1^2+2^2+3^2+...+(n-3)^2 ...3
+ ...
+ 1^2 ...n-1
= (n-1)*1^2+(n-2)*2^2+(n-3)*3^2+...+1*(n-1)^2
n-1
= E (n-k)k^2. (求和符号暂且这样打了)
k=1
【应该说种类是a*b的那一种正方形比较好。一个正方形的一条边如果占据了a*b的空间的话，那么这个正方形从最左边到最右边或者从最上边到最下边的距离就是a+b,用了a+b+1个点。而一个n*n的点阵上 上下和 左右只能包含（n-（a+b+1）+1）=n-a-b个，a*b的这种正方形就有（n-a-b）^2个。
比如n=3时，a=b=1，就是中间的菱形的个数为（3-1-1）^2=1个。小正方形是a*0型，有（3-1-0）^2=4个，大正方形2*0型，有(3-2-0)^2=1个。

Answer 2

先排序，然后枚举任意两个点，在二分查找是否存在两个对称点
*/
#include<iostream>
#include<algorithm>
using namespace std;

struct point{
int x,y;
};
point p[1001];
int n;

int cmp(point a,point b)
{
if( a.x!=b.x )
return a.x<b.x;
else return a.y<b.y;
}

bool search(int x,int y)
{
int l=0,r=n-1;
while( l<=r )
{
int mid=(l+r)/2;
if( p[mid].x==x && p[mid].y==y ) return true;
if( p[mid].x!=x )
{
if( p[mid].x>x ) r=mid-1;
else l=mid+1;
} else {
if( p[mid].y>y ) r=mid-1;
else l=mid+1;
}
}
return false;
}

int main()
{
int i,j;
// freopen("t.txt","r",stdin);
int t;
cin>>t;
while( t-- )
{
while( cin>>n && n )
{
for(i=0;i<n;++i)
cin>>p[i].x>>p[i].y;
sort(p,p+n,cmp);
int cns=0;
for(i=0;i<n;++i)
{
for(j=i+1;j<n;++j)
{
/*
三角形全等，分别求出对应的x,y的坐标
*/
int x1=p[i].x+p[j].y-p[i].y;
int y1=p[i].y+p[i].x-p[j].x;
if( !search(x1,y1) ) continue;
int x2=p[j].x+p[j].y-p[i].y;
int y2=p[j].y+p[i].x-p[j].x;
if( !search(x2,y2) ) continue;
cns++;
}
}
cout<<cns/2<<endl;
}
if( t ) cout<<endl;
}
return 0;
}

Answer 3

定义二维数组，a[n][m]，然后用两次循环语句，for（i=0;i<=n;i++）for（j=0;j<=m;j++）;
希望给出原题~~

追问

原题 给了 ~~~

追答

int n,m,a;
int x[],y[];
scanf("请输入不小于4个的坐标数：%d\n",&n);
for(i=0;i<n;i++);
{
scanf("请输入坐标(%d %d)",x[i]y[i]);
}
让我下午想一想啊！！

Answer 4

我是算法数据结构的老师，你应该知道我是谁吧。我刚把你的QQ拿给朱导了。如果你现在马上向辅导员认错。我就当作没看到。 这道题还是很简单的，关键是用已知2点的坐标推出另外2点的坐标的公式。希望你好好学习算法数据结构！