| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
hash可以564MS过~~/*
题意:在平面直角坐标系给出n个点,问你能组成多少个正方形
此题因为给出n是最大1000大小,所以不可能暴力(n^4)
所以我们可以退而求其次,因为是正方形如果我们知道其中两个点那么另外两个点我们自然可以求出
公式:
u.x=node[i].x+(node[i].y-node[j].y);
u.y=node[i].y-(node[i].x-node[j].x);
v.x=node[j].x+(node[i].y-node[j].y);
v.y=node[j].y-(node[i].x-node[j].x);
这样我们可以这两个点创建一个hash表来找另外两个点
*/
#include<iostream>
#include<queue>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iomanip>
#include<map>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<set>
#define LL long long
#define IT __int64
#define zero(x) fabs(x)<eps
#define mm(a,b) memset(a,b,sizeof(a))
const int INF=0x7fffffff;
const double inf=1e8;
const double eps=1e-10;
const double PI=acos(-1.0);
const int Max=2001;
using namespace std;
int sign(double x)
{
return (x>eps)-(x<-eps);
}
typedef struct Node
{
int x;
int y;
Node(const int &_x=0, const int &_y=0) : x(_x), y(_y) {}
void input()
{
cin>>x>>y;
}
void output()
{
cout<<x<<" "<<y<<endl;
}
}point;
point node[Max];
int hash[Max<<5];
int next[Max];
double xmult(point p0,point p1,point p2)
{
return(p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}
bool cmp(point u,point v)
{
if(u.y<v.y)
return true;
else if(u.y==v.y)
{
if(u.x<v.x)
return true;
}
return false;
}
bool find(int x,int y)
{
int value,index;
value=abs(x+y);
index=hash[value];
while(index!=-1)
{
if(node[index].x==x&&node[index].y==y)
return true;
index=next[index];
}
return false;
}
int main()
{
int n,m,i,j,value,index;
point u,v;
int sum;
//freopen("D:\\in.txt","r",stdin);
while(cin>>n&&n)
{
sum=0;
//map<int,int>Map_x;
//map<int,int>Map_y;
for(i=0;i<n;i++)
{
node[i].input();
//Map_x[node[i].x]=1;
//Map_y[node[i].y]=1;
}
//cout<<Map_x[-1]<<" "<<Map_y[-1]<<endl;
memset(hash,-1,sizeof(hash));
memset(next,-1,sizeof(next));
sort(node,node+n,cmp);
for(i=0;i<n;i++)
{
value=abs(node[i].x+node[i].y);
next[i]=hash[value];
hash[value]=i;
}
for(i=0;i<n;i++)
{
for(j=i+1;j<n;j++)
{
u.x=node[i].x+(node[i].y-node[j].y);
u.y=node[i].y-(node[i].x-node[j].x);
v.x=node[j].x+(node[i].y-node[j].y);
v.y=node[j].y-(node[i].x-node[j].x);
//cout<<u.x<<" "<<u.y<<" "<<v.x<<" "<<v.y<<endl;
if(find(u.x,u.y)&&find(v.x,v.y))
sum+=1;
}
}
cout<<sum/2<<endl;
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator