?? pku 3432 數正方形 哈西表.txt
字號:
#include <stdio.h>
#include <iostream>
#include <stdio.h>
#include <stdio.h>
#include <iostream>
#include <math.h>
#include <stdlib.h>
#include <iomanip>
#include <string.h>
#include <algorithm>
#include <vector>
#include <iterator>
//PKU 3432 數正方形 哈西表
using namespace std;
#define PB push_back
#define PO pop_back
#define INFI 9999999
#define NMAX 2050
#define CMAX 10000
typedef struct opnode
{
int x;
int y;
}opnode;
typedef struct opans
{
opnode sq[4];
}opans;
opnode node[NMAX];
vector <opnode> mmap[CMAX+5];
opans ans[NMAX*NMAX];
bool cmp(opnode a,opnode b)
{
if(a.x==b.x) return a.y<b.y;
else return a.x<b.x;
}
bool same(opans a,opans b)
{
if(a.sq[0].x==b.sq[0].x && a.sq[0].y==b.sq[0].y && a.sq[1].x==b.sq[1].x && a.sq[1].y==b.sq[1].y && a.sq[2].x==b.sq[2].x && a.sq[2].y==b.sq[2].y) return true;
else return false;
}
bool cmp1(opans a,opans b)
{
if(a.sq[0].x==b.sq[0].x)
{
if(a.sq[0].y==b.sq[0].y)
{
if(a.sq[1].x==b.sq[1].x)
{
if(a.sq[1].y==b.sq[1].y)
{
if(a.sq[2].x==b.sq[2].x)
{
return a.sq[2].y<b.sq[2].y;
}
else return a.sq[2].x<b.sq[2].x;
}
else return a.sq[1].y<b.sq[1].y;
}
else return a.sq[1].x<b.sq[1].x;
}
else return a.sq[0].y<b.sq[0].y;
}
else return a.sq[0].x<b.sq[0].x;
}
void hash(int num)
{
int i,qt;
for(i=1;i<=CMAX;i++) mmap[i].clear();
for(i=1;i<=num;i++)
{
qt=(abs(node[i].x)+abs(node[i].y))%CMAX+1;
mmap[qt].PB(node[i]);
}
}
void solve(int num)
{
int i,j,x1,y1,x2,y2,th,flag,sum,totle;
opnode q1,q2;
vector <opnode> :: iterator it;
hash(num);
sum=0;
totle=0;
for(i=1;i<=num;i++)
{
for(j=i+1;j<=num;j++)
{
flag=0;
x1=node[i].x-(node[j].y-node[i].y);
y1=node[i].y+(node[j].x-node[i].x);
x2=node[j].x-(node[j].y-node[i].y);
y2=node[j].y+(node[j].x-node[i].x);
th=(abs(x1)+abs(y1))%CMAX+1;
for(it=mmap[th].begin();it!=mmap[th].end();it++)
{
if((*it).x==x1 && (*it).y==y1) flag++;
}
th=(abs(x2)+abs(y2))%CMAX+1;
for(it=mmap[th].begin();it!=mmap[th].end();it++)
{
if((*it).x==x2 && (*it).y==y2) flag++;
}
if(flag==2)
{
totle++;
ans[totle].sq[0].x=x1; ans[totle].sq[0].y=y1;
ans[totle].sq[1].x=x2; ans[totle].sq[1].y=y2;
ans[totle].sq[2].x=node[i].x; ans[totle].sq[2].y=node[i].y;
ans[totle].sq[3].x=node[j].x; ans[totle].sq[3].y=node[j].y;
sort(ans[totle].sq,ans[totle].sq+4,cmp);
}
flag=0;
x1=node[i].x+(node[j].y-node[i].y);
y1=node[i].y-(node[j].x-node[i].x);
x2=node[j].x+(node[j].y-node[i].y);
y2=node[j].y-(node[j].x-node[i].x);
th=(abs(x1)+abs(y1))%CMAX+1;
for(it=mmap[th].begin();it!=mmap[th].end();it++)
{
if((*it).x==x1 && (*it).y==y1) flag++;
}
th=(abs(x2)+abs(y2))%CMAX+1;
for(it=mmap[th].begin();it!=mmap[th].end();it++)
{
if((*it).x==x2 && (*it).y==y2) flag++;
}
if(flag==2)
{
totle++;
ans[totle].sq[0].x=x1; ans[totle].sq[0].y=y1;
ans[totle].sq[1].x=x2; ans[totle].sq[1].y=y2;
ans[totle].sq[2].x=node[i].x; ans[totle].sq[2].y=node[i].y;
ans[totle].sq[3].x=node[j].x; ans[totle].sq[3].y=node[j].y;
sort(ans[totle].sq,ans[totle].sq+4,cmp);
}
}
}
if(totle==0) {printf("0\n");return;}
sum=1;
sort(ans+1,ans+1+totle,cmp1);
// printf("totle=%d\n",totle);
for(i=2;i<=totle;i++)
{
if(!same(ans[i-1],ans[i])) sum++;
// printf("%d %d %d %d %d %d %d %d\n",ans[i].sq[0].x,ans[i].sq[0].y,ans[i].sq[1].x,ans[i].sq[1].y,ans[i].sq[2].x,ans[i].sq[2].y,ans[i].sq[3].x,ans[i].sq[3].y);
}
printf("%d\n",sum);
}
int main()
{
int i,num;
while(scanf("%d",&num)!=EOF)
{
for(i=1;i<=num;i++)
scanf("%d %d",&node[i].x,&node[i].y);
solve(num);
}
return 0;
}
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -