DOOOR
题意
一张点图由两张相同的点图错位放置得到,有多少种向量使得其中的某些点沿向量移动可以到其他的点
思路
思维题
1000的n,考虑枚举这样的向量,再注意检验 (n^2)
枚举只用考虑一个点的移动情况,
一个点要么移到别的点,要么被别的点移动到,只要每个点正反方向移动能找到一个匹配的点,那这个向量就是合法的,存起来
那为什么开始要sort呢!!!!!!!!!
//j
#include <bits/stdc++.h>
using namespace std;
int ans,n;
bool mark[7004][7004];
//最大向量+-2000,范围2000,
struct node{
int x,y;
}e[1004];
bool check(int dx,int dy){
for(int i=1;i<=n;i++){
if((!mark[e[i].x+dx][e[i].y+dy])&&(!mark[e[i].x-dx][e[i].y-dy]))return 0;
//两个方向移动都找不到重合点
}
return 1;
}
bool cmp(node x,node y){
if(x.x!=y.x)return x.x<y.x;
else return x.y<y.y;
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>e[i].x>>e[i].y;
e[i].x+=3000,e[i].y+=3000;
mark[e[i].x][e[i].y]=1;
//有负的!!!! 加了向量有还可能是负数
}
sort(e+1,e+1+n,cmp);
//谁能告诉我为什么要 sort!!!!!!!!!!!!!!!!!!
for(int i=2;i<=n;i++){
int dx=e[i].x-e[1].x;
int dy=e[i].y-e[1].y;
if(check(dx,dy))ans+=2;
}
cout<<ans;
}
}