Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

hash可以564MS过~~

Posted by ecjtu_yuweiwei at 2014-07-31 18:09:21 on Problem 2002
/*
题意:在平面直角坐标系给出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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator