题面

题意:有10w个点,问你选4个点,能组成平行于坐标轴的正方形有多少个

题解:不知道正解,我的做法就是暴力的基础上优化一点,每次按x排好序,每次枚举的2个点都是x相同的

这样算是个优化?但并不能过,因为可能一列全是x相同的,于是又判了一次对于这个点,x相同的多还是y相同的多

具体实现用了个set没想到就过了

 #include<bits/stdc++.h>
using namespace std;
#define N 2000006
set<int>x[N],y[N];
int n,a[N],b[N],ans=;
int main()
{
scanf("%d",&n);
for (int i=;i<=n;i++)
{
scanf("%d%d",&a[i],&b[i]);
a[i]+=1e6;b[i]+=1e6;
x[a[i]].insert(b[i]);
y[b[i]].insert(a[i]);
}
for (int i=;i<=n;i++)
{
if (x[a[i]].size()<y[b[i]].size())
{
set<int>::iterator it=x[a[i]].upper_bound(b[i]);
while (it!=x[a[i]].end())
{
int l=*it-b[i];
if (a[i]+l<N)
if (x[a[i]+l].find(b[i]+l)!=x[a[i]+l].end() && x[a[i]+l].find(b[i])!=x[a[i]+l].end()) ans++;
it++;
}
}else
{
set<int>::iterator it=y[b[i]].upper_bound(a[i]);
while (it!=y[b[i]].end())
{
int l=*it-a[i];
if (b[i]+l<N)
if (y[b[i]+l].find(a[i]+l)!=y[b[i]+l].end() && y[b[i]+l].find(a[i])!=y[b[i]+l].end()) ans++;
it++;
}
}
}
cout<<ans<<endl;
}

最新文章

  1. ScrollView中嵌套GridView,ListView只显示一行的解决办法
  2. 知识联结梳理 : I/O多路复用、EPOLL(SELECT/POLL)、NIO、Event-driven、Reactor模式
  3. KEIL MDK STM32如何建立工程
  4. linux 下 文件权限和文件主
  5. jstl long类型数据转换为日期格式
  6. static class - 静态类
  7. kafka 的 createDirectStream
  8. Redis in Docker on Linux Container
  9. mybatis_SQL映射(4)鉴别器
  10. 南阳OJ-6-喷水装置(一)
  11. vue-输入框change事件并获取值
  12. 先安装VS后安装IIS,注册IIS方法
  13. 《FPGA全程进阶---实战演练》第七章 让按键恢复平静
  14. 给PHP开启shmop扩展实现共享内存
  15. C# 初学
  16. c++ 指定长度容器元素的拷贝(copy_n)
  17. iOS开发值得收藏的博客
  18. Java解决LeetCode72题 Edit Distance
  19. Lifecycle for overriding binding, validation, etc,易于同其它View框架(Tiles等)无缝集成,采用IOC便于测试。
  20. MySQL5.7 添加、删除用户与授权

热门文章

  1. P2041 分裂游戏
  2. ubuntu 14.04 挂载window共享目录
  3. 本地搭建easy-mock
  4. 爬虫之pyquery库
  5. 【转】Flex 布局
  6. Python运算符(Python学习笔记03)
  7. [bzoj1833][ZJOI2010][count] (数位dp)
  8. linux下安装并配置vim
  9. 常见mysql的数据迁移
  10. 自己定义控件:onDraw 方法实现仿 iOS 的开关效果