- 浏览: 196555 次
- 性别:
- 来自: 武汉
文章分类
- 全部博客 (137)
- c++ (74)
- c++,算法,回溯 (2)
- DP问题。 (9)
- DP问题,0/1背包问题 (3)
- 数学问题 (6)
- 贪心算法 (10)
- 排序 (16)
- 数据结构 (7)
- 容器 (2)
- 模拟问题 (2)
- 水题 (8)
- 并查集 (3)
- 非技术 (2)
- 素数问题 (1)
- DFS (3)
- 二叉树 (1)
- 递归 (1)
- 图论 (5)
- 最小生成树 (5)
- 最短路径 (6)
- bell_flaod算法 (2)
- hash (3)
- 二分查找 (1)
- 搜索 (5)
- BFS (5)
- STL (3)
- 字符串hash (1)
- 拓扑排序 (1)
- 字典树 (4)
- 哈弗曼树 (1)
- KMP (7)
- 线段树 (9)
- 树状数组 (6)
- 全排列 (2)
- DP问题 (2)
- LCS (1)
- 最长不下降子序列 (2)
- 面试经验 (3)
题意:在平面内给出n个点,问你这些点一共能组成几个不相等的正方形? 思路:几何 + 二分。先排序,然后枚举任意两点(x1,y1)(x2,y2),则如果存在点(x1+y1-y2,y1-x1+x2)(x2+y1-y2,y2-x1+x2)则它们能构成一个正方形(这里方向是确定的,否则还有一种可能)。所以用二分查询是否存在这两个点,有的话ans就+1。最后的ans要/2,因为正方形都重复算了一次。
至于本题关于hash的算法将会进一步阐述……
关于二分查找的代码如下:#include<iostream>
#include<algorithm>
using namespace std;
const int Max = 1005;
struct data
{
int x, y;
}node[Max];
bool cmp(const data &a, const data &b)
{ // 由于下面调用的binary_search(),故要用加const。
if(a.x == b.x)
return a.y < b.y;
return a.x < b.x;
}
int main()
{
int n, i, j;
while(scanf("%d", &n) && n)
{
for(i = 0; i < n; i ++)
scanf("%d%d", &node[i].x, &node[i].y);
sort(node, node + n, cmp);
// 先排序。这里自己要注意:x相等的y问题不用二维的二分,直接cmp,要理解清楚,就一顺序。
int ans = 0;
for(i = 0; i < n; i ++)
for(j = i + 1; j < n; j ++)
{
data tmp;
tmp.x = node[i].x + node[i].y - node[j].y;
tmp.y = node[i].y - node[i].x + node[j].x;
if(!binary_search(node, node + n, tmp, cmp)) // 学会STL的二分。
continue;
tmp.x = node[j].x + node[i].y - node[j].y;
tmp.y = node[j].y - node[i].x + node[j].x;
if(!binary_search(node, node + n, tmp, cmp))
continue;
ans ++;
}
printf("%d\n", ans/2);
}
return 0;
}
发表评论
-
虚函数、纯虚函数、虚基类、抽象类、虚函数继承、虚继承
2013-08-29 14:34 785虚函数:虚函数是C++中用于实现多态(polymorphis ... -
排序算法总结
2013-05-17 11:00 783选择排序、快速排序、希尔排序、堆排序不是稳定的排序算法, ... -
poj 3122
2012-12-11 19:51 807题意:作者要开一个生日party,他现在拥有n块高度都为1 ... -
poj 3273
2012-12-11 16:49 945题意:给你天数n,和每天需要花的钱,让你把这些天分成m份(每份 ... -
字典树学习材料
2012-05-30 14:29 932字典树,又称单词查找树,Trie树,是一种树形结构,典型应 ... -
poj 1159
2012-05-28 19:08 1396题目大意:给你一段字符串,让你求出在中间最少加入几个字符 ... -
poj 3176
2012-05-28 14:47 975大致题意: 输入一个n层的三角形,第i层有i个数,求从第 ... -
poj 1260
2012-05-28 09:54 1570题意解释: 有n个等级的珠宝,等级依次升高,等级越高价钱越高 ... -
poj 1836
2012-05-28 09:22 2670是POJ2533的扩展题。题意不难,令到原队列 ... -
poj 2533
2012-05-26 15:36 1206在做这道题目之前,首先让我们了解一下什么是LIS算法,LIS俗 ... -
poj 3267
2012-05-26 09:43 774从程序可以看出,第i个位置到L所删除的字符数,总是先取最坏情况 ... -
poj 1276
2012-05-25 16:20 2350题意: 这道题的意思是给你一堆钱,各种面值的都有,比 ... -
poj 1094
2012-05-25 13:54 1062题意:给出字母个数,和有限个有序对(a<b)求出能确定字 ... -
poj 3393
2012-05-23 17:00 1225大致题意: 科普文一篇,文章80%都是无用信息,因为 ... -
poj 3007
2012-05-14 10:21 949大致题意: 给定一个字符串,从任意位置把它切为两半, ... -
poj 3096
2012-05-10 21:09 962题意: 定义D-pairs表示取字符串s中相距为D的两个字母 ... -
poj 1426
2012-04-26 20:11 2116大致题意: 给出一个整数n,(1 <= n <= ... -
poj 1797
2012-04-24 15:05 1590题目大意是就是何处一个图,n个顶点和m条边,每个边都有最大承载 ... -
poj 1338
2012-04-23 10:20 1220题意:题目意思是求由2,3,5的乘积组成的数从大到小排列,从1 ... -
poj 2021
2012-04-19 15:00 893题意:Ted今年100岁,给出n对他家族的关系:“父 ...
相关推荐
北大POJ2002-Squares 解题报告+AC代码
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
选择了三道经典的二分查找的poj模拟题,有利于读者对二分查找的深刻把握
poj 百练 题目分类 poj 百练 题目分类
poj分类poj分类poj分类poj分类
pojACM题目分类,便于各类型同学分别做题有所参考
POJ题目分类POJ题目分类POJ题目分类
该文档对poj大部分题目进行了分类,有利于喜欢在poj刷题的朋友
poj题目分类
POJ题目分类,列出了所有的类目,里面写了一些很好的框架。
poj题目分类打包 acm北大的题库题目分类 来源网络 网络还有自己整理一部分。好久前的玩意了
史上最全poj题目分类及原题 包括:基本算法:贪心、递归、递推、枚举;基本数据结构,链表、栈;动态规划;搜索;高级数据结构:二叉搜索树、线段树、树状数组;数学:数论
强大的poj分类 学做POJ必备 非最新,供参考
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
史上最全poj题目分类(159页).pdf
POJ题解及题目分类,共150道左右。C/C++
poj题目分类 简单题 搜索题 模拟题 动态规划 计算几何 递推 数学题 图论 数据结构 贪心 构造 枚举 特殊问题特殊对待 博弈 适合学算法的人进行专项练习
poj 1064 代码,二分查找的应用,没啥说的,看看
ACM/icpc的练习题目分类,非常全面的关于poj题目的分类
关于poj dp分类,我一直寻找dp的分类,终于找到了,也上传一下