【NOIP模拟】四轮车

题面

在地图上散落着 n 个车轮，小 J 想用它们造一辆车。要求如下：

1. 一辆车需要四个车轮，且四个车轮构成一个正方形

2. 车轮不能移动你需要计算有多少种造车的方案（两个方案不同当且仅当所用车轮不全相同，坐标相同的两个车轮视为不同车轮）。

30%的数据保证 n ≤ 30
100%的数据保证 1 ≤ n ≤ 1000; |x|, |y| < 20000

分析

其实和这个题一样的思路。就不赘述了。

然而为什么要发这篇题解，因为这个题地图范围更大，二维数组存不下，于是我又双叒被map教做人了！！（本周第三次）

所以这篇题解仅仅小小讨论一下STL这群坑比

我去访问有没有这个点对，以及出现了多少次的时候 我是这样写的

我自己用clock测出来跑了4000多ms，我坚信这不科学啊，我写的一定是正解，肯定是机子太老年了，于是写完题玩了一个多小时。。

然后就真的挂了。。

后来调用机房几个dalao也没瞅出来问题在哪，在我的一番试验和推测过后，终于找到了！！

大概是我访问了不存在的元素！！因为map内部是二分查找吧？？查不到，这可凉凉。

正确姿势 

意思就是，一定要判一下这个元素是不是存在，再取它的个数。这样从4000+ms ---> 100+ms

还有一些其他存法，比如bitset，因为40000*40000的地图是肯定开不下的嗷。。

于是

而256M的内存可以申请的bitset是8*1024*1024*256=2147483648，是能够开的下的

用的时候偏移一下

这样比map跑得更快

贴个简化的代码，能避开STL的坑点尽量避开吧

代码

1. #include<bits/stdc++.h>  
2. using namespace std;  
3. #define N 1010  
4. #define RT register  
5. int n,ans;  
6. int x[N],y[N];  
7. map<pair<int,int>,int>mp;  
8. template<class T>  
9. inline void read(T &x)  
10. {  
11.     x=0;int f=1;static char ch=getchar();  
12.     while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}  
13.     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}  
14.     x*=f;  
15. }  
16. int main()  
17. {  
18.     read(n);  
19.     for(RT int i=1;i<=n;i++)read(x[i]),read(y[i]),mp[make_pair(x[i],y[i])]=1;  
20.     for(RT int i=1;i<=n;i++)  
21.     {  
22.         for(RT int j=i+1;j<=n;j++)  
23.         {  
24.             int a=x[i],b=y[i],c=x[j],d=y[j];  
25.             int dx=abs(a-c),dy=abs(d-b);  
26.             int x1=c-dy,y1=d+dx,x2=a-dy,y2=b+dx;  
27.             if(mp[make_pair(x1,y1)]&&mp[make_pair(x2,y2)])ans++;      
28.         }     
29.     }   
30.     printf("%d\n",ans/2);     
31.     return 0;  
32. }