小美女奶昔——视察新家，多图~~# pets - 心有所宠
h*e
1 楼
rt
给定平面上n点，求在同一直线上最多点问题～～大家用double /float 类型作hash
key么？
判断两个double /float 类型相等～～～ 靠谱么
给定平面上n点，求在同一直线上最多点问题～～大家用double /float 类型作hash
key么？
判断两个double /float 类型相等～～～ 靠谱么
f*s
2 楼
以前搜索citation的时候无意中在一个数据库看到了我在中国的专利，都被翻译过来了
，而且格式也很规范。有谁知道是哪个数据库吗？或者哪个数据库的中国专利格式比较
规范的，麻烦分享一下。有包子答谢。
，而且格式也很规范。有谁知道是哪个数据库吗？或者哪个数据库的中国专利格式比较
规范的，麻烦分享一下。有包子答谢。
H*7
3 楼
慢慢的会知道的42件事
佛经上181条做人的道理
人生成熟的四个重要标志
人生应该记住的16句话
佛家经典禅语语录句子
改变人生的16个妙方
人生就要悟
感悟生活的真谛
11个笑话让你领悟人生
人一生要读的60本书（经典读书计划
女人一生的精彩
经典人生感悟生活感悟(推荐)
年轻时应该知道的道理
世界上最美丽的英文——人生短篇
编织人生：人生三十六字诀
成功秘诀
人生成功的21个信念
塑造阳光心态
成大事必备9种能力、9种手段、9种
我们工作到底为了什么--强烈推荐
如何正确的进行人生规划
改变你人生的50种方法
每天读一遍这7句话，让你更加自信
十七条黄金定律(拿破仑·希尔)
哈佛成功金言
自我激励的20个方法
年轻人应该谨记的十点
人生成败关键在于心态
成功人士的二十个习惯
时间管理101招
战胜自我就是成功
佛经上181条做人的道理
人生成熟的四个重要标志
人生应该记住的16句话
佛家经典禅语语录句子
改变人生的16个妙方
人生就要悟
感悟生活的真谛
11个笑话让你领悟人生
人一生要读的60本书（经典读书计划
女人一生的精彩
经典人生感悟生活感悟(推荐)
年轻时应该知道的道理
世界上最美丽的英文——人生短篇
编织人生：人生三十六字诀
成功秘诀
人生成功的21个信念
塑造阳光心态
成大事必备9种能力、9种手段、9种
我们工作到底为了什么--强烈推荐
如何正确的进行人生规划
改变你人生的50种方法
每天读一遍这7句话，让你更加自信
十七条黄金定律(拿破仑·希尔)
哈佛成功金言
自我激励的20个方法
年轻人应该谨记的十点
人生成败关键在于心态
成功人士的二十个习惯
时间管理101招
战胜自我就是成功
R*0
4 楼
自上周一与猫爸猫妈亲密接触以后，奶昔饮食正常，情绪稳(fanfu)定(wuchang)，曾经
被当成砂盆的南瓜窝也变成了好地方~~
每天晚饭时间，可乐和雪碧被邀请到包厢享受大餐，奶昔闻着俩陌生喵的味道淡去，小
心地踱到门外，四处张望
坐得好累，趴一会，翻过来，又翻过去，似乎真的没有什么危险了
这个黑黑的大盒子是什么东西，上去看看
啊，这里看起来很隐蔽，是个休息的好地方
没人看我吧，我去那边开阔地带转转
不好！有人来了！赶紧找机会回去！
就这样，奶昔每天在外面晃悠的时间越来越长，直到有一天，在被猫妈试图抚摸未果的
几分钟后勇敢地攻击了猫妈，为自己好好出了口气，然后，被关小黑屋三天。。。再然
后，被强迫剪了所有指甲。。。各种血泪描述详见以下回帖
http://www.mitbbs.com/article_t1/pets/32759971_0_2.html
http://www.mitbbs.com/article_t/pets/32759665.html
奶昔是不是自此就痛定思痛，决心重新做喵了呢？究竟什么时候可乐雪碧才可以安全见
到这位美若冰霜的小妹妹呢？让我们怀着最美好的期待吧~~
被当成砂盆的南瓜窝也变成了好地方~~
每天晚饭时间，可乐和雪碧被邀请到包厢享受大餐，奶昔闻着俩陌生喵的味道淡去，小
心地踱到门外，四处张望
坐得好累，趴一会，翻过来，又翻过去，似乎真的没有什么危险了
这个黑黑的大盒子是什么东西，上去看看
啊，这里看起来很隐蔽，是个休息的好地方
没人看我吧，我去那边开阔地带转转
不好！有人来了！赶紧找机会回去！
就这样，奶昔每天在外面晃悠的时间越来越长，直到有一天，在被猫妈试图抚摸未果的
几分钟后勇敢地攻击了猫妈，为自己好好出了口气，然后，被关小黑屋三天。。。再然
后，被强迫剪了所有指甲。。。各种血泪描述详见以下回帖
http://www.mitbbs.com/article_t1/pets/32759971_0_2.html
http://www.mitbbs.com/article_t/pets/32759665.html
奶昔是不是自此就痛定思痛，决心重新做喵了呢？究竟什么时候可乐雪碧才可以安全见
到这位美若冰霜的小妹妹呢？让我们怀着最美好的期待吧~~
y*n
5 楼
不是可以设一个比较小的数， 0.0000001， 然后和这个数比较就可以吗？
z*i
6 楼
点播三：人生成熟的四个重要标志
我觉得这个应该最短
慢慢的会知道的42件事
佛经上181条做人的道理
人生成熟的四个重要标志
人生应该记住的16句话
佛家经典禅语语录句子
改变人生的16个妙方
人生就要悟
感悟生活的真谛
11个笑话让你领悟人生
人一生要读的60本书（经典读书计划
女人一生的精彩
经典人生感悟生活感悟(推荐)
年轻时应该知道的道理
世界上最美丽的英文——人生短篇
编织人生：人生三十六字诀
成功秘诀
人生成功的21个信念
塑造阳光心态
成大事必备9种能力、9种手段、9种
我们工作到底为了什么--强烈推荐
如何正确的进行人生规划
改变你人生的50种方法
每天读一遍这7句话，让你更加自信
十七条黄金定律(拿破仑·希尔)
哈佛成功金言
自我激励的20个方法
年轻人应该谨记的十点
人生成败关键在于心态
成功人士的二十个习惯
时间管理101招
战胜自我就是成功
【在 H******7 的大作中提到】
: 慢慢的会知道的42件事
: 佛经上181条做人的道理
: 人生成熟的四个重要标志
: 人生应该记住的16句话
: 佛家经典禅语语录句子
: 改变人生的16个妙方
: 人生就要悟
: 感悟生活的真谛
: 11个笑话让你领悟人生
: 人一生要读的60本书（经典读书计划
我觉得这个应该最短
慢慢的会知道的42件事
佛经上181条做人的道理
人生成熟的四个重要标志
人生应该记住的16句话
佛家经典禅语语录句子
改变人生的16个妙方
人生就要悟
感悟生活的真谛
11个笑话让你领悟人生
人一生要读的60本书（经典读书计划
女人一生的精彩
经典人生感悟生活感悟(推荐)
年轻时应该知道的道理
世界上最美丽的英文——人生短篇
编织人生：人生三十六字诀
成功秘诀
人生成功的21个信念
塑造阳光心态
成大事必备9种能力、9种手段、9种
我们工作到底为了什么--强烈推荐
如何正确的进行人生规划
改变你人生的50种方法
每天读一遍这7句话，让你更加自信
十七条黄金定律(拿破仑·希尔)
哈佛成功金言
自我激励的20个方法
年轻人应该谨记的十点
人生成败关键在于心态
成功人士的二十个习惯
时间管理101招
战胜自我就是成功
【在 H******7 的大作中提到】
: 慢慢的会知道的42件事
: 佛经上181条做人的道理
: 人生成熟的四个重要标志
: 人生应该记住的16句话
: 佛家经典禅语语录句子
: 改变人生的16个妙方
: 人生就要悟
: 感悟生活的真谛
: 11个笑话让你领悟人生
: 人一生要读的60本书（经典读书计划
K*a
7 楼
赞多图！！！！奶昔太美了，看起来自在了不少啊。希望尽快和谐！！
h*e
8 楼
找到一个链接，关于float做key
“HOWEVER, you should not be using a floating point for any part of a key in
any map -- for the same reason you shouldn't use them with == and !=
operators. Since floating points are approximations, they are unreliable as
keys.“
http://www.cplusplus.com/forum/beginner/56918/
【在 y***n 的大作中提到】
: 不是可以设一个比较小的数， 0.0000001， 然后和这个数比较就可以吗？
“HOWEVER, you should not be using a floating point for any part of a key in
any map -- for the same reason you shouldn't use them with == and !=
operators. Since floating points are approximations, they are unreliable as
keys.“
http://www.cplusplus.com/forum/beginner/56918/
【在 y***n 的大作中提到】
: 不是可以设一个比较小的数， 0.0000001， 然后和这个数比较就可以吗？
H*g
9 楼
哈佛成功金言 跟哈图十五有什么关系吗？
R*0
10 楼
啊，酥酥妈，你这也太神速了~~昨晚把硬壳carrier放进奶昔的房间了，让她先熟悉熟
悉，看她什么时候愿意进去了，就跟可乐雪碧见一面看看
【在 K***a 的大作中提到】
: 赞多图！！！！奶昔太美了，看起来自在了不少啊。希望尽快和谐！！
悉，看她什么时候愿意进去了，就跟可乐雪碧见一面看看
【在 K***a 的大作中提到】
: 赞多图！！！！奶昔太美了，看起来自在了不少啊。希望尽快和谐！！
s*x
11 楼
Cc150 介绍的非常清楚了吧？
R*a
12 楼
就是四个部位长毛了
【在 z***i 的大作中提到】
: 点播三：人生成熟的四个重要标志
: 我觉得这个应该最短
:
: 慢慢的会知道的42件事
: 佛经上181条做人的道理
: 人生成熟的四个重要标志
: 人生应该记住的16句话
: 佛家经典禅语语录句子
: 改变人生的16个妙方
: 人生就要悟
m*u
13 楼
赞美女
h*e
14 楼
记不清了，能告诉一下第几章地几题么。
【在 s**x 的大作中提到】
: Cc150 介绍的非常清楚了吧？
【在 s**x 的大作中提到】
: Cc150 介绍的非常清楚了吧？
m*d
15 楼
第一个标志是熟记哈佛校训十二亿条
【在 z***i 的大作中提到】
: 点播三：人生成熟的四个重要标志
: 我觉得这个应该最短
:
: 慢慢的会知道的42件事
: 佛经上181条做人的道理
: 人生成熟的四个重要标志
: 人生应该记住的16句话
: 佛家经典禅语语录句子
: 改变人生的16个妙方
: 人生就要悟
【在 z***i 的大作中提到】
: 点播三：人生成熟的四个重要标志
: 我觉得这个应该最短
:
: 慢慢的会知道的42件事
: 佛经上181条做人的道理
: 人生成熟的四个重要标志
: 人生应该记住的16句话
: 佛家经典禅语语录句子
: 改变人生的16个妙方
: 人生就要悟
c*y
16 楼
奶昔太漂亮了太漂亮了 而且手感一定很好~~~
可喜可贺啊都出来玩儿了
到时候是不是要跟原住民分别会面啊？不然她会不会以为那俩合伙欺负她。。。。
可喜可贺啊都出来玩儿了
到时候是不是要跟原住民分别会面啊？不然她会不会以为那俩合伙欺负她。。。。
j*8
17 楼
正准备发个类似的问题，就在这里说了
有人面这题时因为用 double / float 作为 hashmap的key而被面试官说的吗？？
有人面这题时因为用 double / float 作为 hashmap的key而被面试官说的吗？？
H*g
18 楼
大波， 励志
q*6
19 楼
奶昔还是越看越爱啊。。。看到你们一家帮她剪指甲那段我也不厚道的笑了。。。。
奶昔和两个原住民会不会变成郭芙和大武，小武的关系啊，哈哈啊哈
【在 R******0 的大作中提到】
: 自上周一与猫爸猫妈亲密接触以后，奶昔饮食正常，情绪稳(fanfu)定(wuchang)，曾经
: 被当成砂盆的南瓜窝也变成了好地方~~
: 每天晚饭时间，可乐和雪碧被邀请到包厢享受大餐，奶昔闻着俩陌生喵的味道淡去，小
: 心地踱到门外，四处张望
: 坐得好累，趴一会，翻过来，又翻过去，似乎真的没有什么危险了
: 这个黑黑的大盒子是什么东西，上去看看
: 啊，这里看起来很隐蔽，是个休息的好地方
: 没人看我吧，我去那边开阔地带转转
: 不好！有人来了！赶紧找机会回去！
: 就这样，奶昔每天在外面晃悠的时间越来越长，直到有一天，在被猫妈试图抚摸未果的
奶昔和两个原住民会不会变成郭芙和大武，小武的关系啊，哈哈啊哈
【在 R******0 的大作中提到】
: 自上周一与猫爸猫妈亲密接触以后，奶昔饮食正常，情绪稳(fanfu)定(wuchang)，曾经
: 被当成砂盆的南瓜窝也变成了好地方~~
: 每天晚饭时间，可乐和雪碧被邀请到包厢享受大餐，奶昔闻着俩陌生喵的味道淡去，小
: 心地踱到门外，四处张望
: 坐得好累，趴一会，翻过来，又翻过去，似乎真的没有什么危险了
: 这个黑黑的大盒子是什么东西，上去看看
: 啊，这里看起来很隐蔽，是个休息的好地方
: 没人看我吧，我去那边开阔地带转转
: 不好！有人来了！赶紧找机会回去！
: 就这样，奶昔每天在外面晃悠的时间越来越长，直到有一天，在被猫妈试图抚摸未果的
s*x
20 楼
自己查查
【在 h*******e 的大作中提到】
: 记不清了，能告诉一下第几章地几题么。
【在 h*******e 的大作中提到】
: 记不清了，能告诉一下第几章地几题么。
l*o
21 楼
有谁知道鸡汤喝多了什么后果？
R*0
22 楼
谢谢~~
【在 m*******u 的大作中提到】
: 赞美女
【在 m*******u 的大作中提到】
: 赞美女
h*e
23 楼
翻了一遍没找到，好久不看了。
你用第四版吧 我是第五版，
第四版10.6 找到了， java 可以自定义类型作为key的，c++ 就不行。
【在 s**x 的大作中提到】
: 自己查查
你用第四版吧 我是第五版，
第四版10.6 找到了， java 可以自定义类型作为key的，c++ 就不行。
【在 s**x 的大作中提到】
: 自己查查
H*g
24 楼
尿频得跟静芬一样
【在 l*****o 的大作中提到】
: 有谁知道鸡汤喝多了什么后果？
【在 l*****o 的大作中提到】
: 有谁知道鸡汤喝多了什么后果？
R*0
25 楼
哈哈，手感确实不错啊，就是短期内不敢再摸，实在是有阴影。。。你这个担心确实有
道理呐，到时候让可乐和雪碧分别出现吧，多少能减少一点紧张吧
【在 c******y 的大作中提到】
: 奶昔太漂亮了太漂亮了 而且手感一定很好~~~
: 可喜可贺啊都出来玩儿了
: 到时候是不是要跟原住民分别会面啊？不然她会不会以为那俩合伙欺负她。。。。
道理呐，到时候让可乐和雪碧分别出现吧，多少能减少一点紧张吧
【在 c******y 的大作中提到】
: 奶昔太漂亮了太漂亮了 而且手感一定很好~~~
: 可喜可贺啊都出来玩儿了
: 到时候是不是要跟原住民分别会面啊？不然她会不会以为那俩合伙欺负她。。。。
p*e
26 楼
可以取整，我就是这样做的
int slope = (int)(1000000.*float(p2.y-p1.y)/(p2.x-p1.x));
int slope = (int)(1000000.*float(p2.y-p1.y)/(p2.x-p1.x));
K*a
27 楼
哈哈哈，我当时picture了一下他们穿的厚厚的样子真心笑得不行了。MM总是特别有想
象力LOL
【在 q***6 的大作中提到】
: 奶昔还是越看越爱啊。。。看到你们一家帮她剪指甲那段我也不厚道的笑了。。。。
: 奶昔和两个原住民会不会变成郭芙和大武，小武的关系啊，哈哈啊哈
象力LOL
【在 q***6 的大作中提到】
: 奶昔还是越看越爱啊。。。看到你们一家帮她剪指甲那段我也不厚道的笑了。。。。
: 奶昔和两个原住民会不会变成郭芙和大武，小武的关系啊，哈哈啊哈
s*x
28 楼
第五版7.6
【在 h*******e 的大作中提到】
: 翻了一遍没找到，好久不看了。
: 你用第四版吧 我是第五版，
: 第四版10.6 找到了， java 可以自定义类型作为key的，c++ 就不行。
R*0
29 楼
凌乱了。。。可乐也是小女猫。。。我倒是想过和谐以后，奶昔会让可乐雪碧更黏糊一
点，现在俩猫都不会一起抱着睡觉互相舔毛什么的
【在 q***6 的大作中提到】
: 奶昔还是越看越爱啊。。。看到你们一家帮她剪指甲那段我也不厚道的笑了。。。。
: 奶昔和两个原住民会不会变成郭芙和大武，小武的关系啊，哈哈啊哈
点，现在俩猫都不会一起抱着睡觉互相舔毛什么的
【在 q***6 的大作中提到】
: 奶昔还是越看越爱啊。。。看到你们一家帮她剪指甲那段我也不厚道的笑了。。。。
: 奶昔和两个原住民会不会变成郭芙和大武，小武的关系啊，哈哈啊哈
h*e
30 楼
谢谢看到cc150给的方法了。觉得给的解法还是比较一般。。。计算几何里面很少用k
来决定点在一条直线上。k在靠近原点一小变很可能导致点在 距离原点远处一大变。
【在 s**x 的大作中提到】
:
: 第五版7.6
来决定点在一条直线上。k在靠近原点一小变很可能导致点在 距离原点远处一大变。
【在 s**x 的大作中提到】
:
: 第五版7.6
c*y
31 楼
奶昔尾巴还垂着 这娃戒心有多重啊。。。。。。
碰玩具不？喜欢catnip不？大鸟玩不玩？
碰玩具不？喜欢catnip不？大鸟玩不玩？
g*e
32 楼
如果坐标是整数的话，斜率都是有理数。可以存pair
【在 h*******e 的大作中提到】
: rt
: 给定平面上n点，求在同一直线上最多点问题～～大家用double /float 类型作hash
: key么？
: 判断两个double /float 类型相等～～～ 靠谱么
【在 h*******e 的大作中提到】
: rt
: 给定平面上n点，求在同一直线上最多点问题～～大家用double /float 类型作hash
: key么？
: 判断两个double /float 类型相等～～～ 靠谱么
g*y
33 楼
有的猫猫很需要耐心啊。。 我养了10年的猫，搬到新家也是藏床底下几个月。。。。
基本上我门回家才出来转悠一小会儿。。
【在 R******0 的大作中提到】
: 自上周一与猫爸猫妈亲密接触以后，奶昔饮食正常，情绪稳(fanfu)定(wuchang)，曾经
: 被当成砂盆的南瓜窝也变成了好地方~~
: 每天晚饭时间，可乐和雪碧被邀请到包厢享受大餐，奶昔闻着俩陌生喵的味道淡去，小
: 心地踱到门外，四处张望
: 坐得好累，趴一会，翻过来，又翻过去，似乎真的没有什么危险了
: 这个黑黑的大盒子是什么东西，上去看看
: 啊，这里看起来很隐蔽，是个休息的好地方
: 没人看我吧，我去那边开阔地带转转
: 不好！有人来了！赶紧找机会回去！
: 就这样，奶昔每天在外面晃悠的时间越来越长，直到有一天，在被猫妈试图抚摸未果的
基本上我门回家才出来转悠一小会儿。。
【在 R******0 的大作中提到】
: 自上周一与猫爸猫妈亲密接触以后，奶昔饮食正常，情绪稳(fanfu)定(wuchang)，曾经
: 被当成砂盆的南瓜窝也变成了好地方~~
: 每天晚饭时间，可乐和雪碧被邀请到包厢享受大餐，奶昔闻着俩陌生喵的味道淡去，小
: 心地踱到门外，四处张望
: 坐得好累，趴一会，翻过来，又翻过去，似乎真的没有什么危险了
: 这个黑黑的大盒子是什么东西，上去看看
: 啊，这里看起来很隐蔽，是个休息的好地方
: 没人看我吧，我去那边开阔地带转转
: 不好！有人来了！赶紧找机会回去！
: 就这样，奶昔每天在外面晃悠的时间越来越长，直到有一天，在被猫妈试图抚摸未果的
h*e
34 楼
如果是pair作为 key 的话自定义的hash 函数一般怎么写
在 c++ unordered_set, int> 大牛给讲一下哦。
【在 g*********e 的大作中提到】
: 如果坐标是整数的话，斜率都是有理数。可以存pair
在 c++ unordered_set
【在 g*********e 的大作中提到】
: 如果坐标是整数的话，斜率都是有理数。可以存pair
w*2
35 楼
哈哈，小美妞出来了，慢慢地会占领每一间房
g*e
36 楼
你写的对
【在 h*******e 的大作中提到】
: 如果是pair作为 key 的话自定义的hash 函数一般怎么写
: 在 c++ unordered_set, int> 大牛给讲一下哦。
【在 h*******e 的大作中提到】
: 如果是pair作为 key 的话自定义的hash 函数一般怎么写
: 在 c++ unordered_set
R*0
37 楼
就是就是，想象力超越一切世俗的禁锢~~
【在 K***a 的大作中提到】
: 哈哈哈，我当时picture了一下他们穿的厚厚的样子真心笑得不行了。MM总是特别有想
: 象力LOL
【在 K***a 的大作中提到】
: 哈哈哈，我当时picture了一下他们穿的厚厚的样子真心笑得不行了。MM总是特别有想
: 象力LOL
h*e
38 楼
光是这个过不了leetcode的编译器阿，需要自定义hash 函数，和比较函数的似乎。
【在 g*********e 的大作中提到】
: 你写的对
【在 g*********e 的大作中提到】
: 你写的对
I*e
39 楼
出了口气马上被关三天，LOL..
美猫！
【在 R******0 的大作中提到】
: 自上周一与猫爸猫妈亲密接触以后，奶昔饮食正常，情绪稳(fanfu)定(wuchang)，曾经
: 被当成砂盆的南瓜窝也变成了好地方~~
: 每天晚饭时间，可乐和雪碧被邀请到包厢享受大餐，奶昔闻着俩陌生喵的味道淡去，小
: 心地踱到门外，四处张望
: 坐得好累，趴一会，翻过来，又翻过去，似乎真的没有什么危险了
: 这个黑黑的大盒子是什么东西，上去看看
: 啊，这里看起来很隐蔽，是个休息的好地方
: 没人看我吧，我去那边开阔地带转转
: 不好！有人来了！赶紧找机会回去！
: 就这样，奶昔每天在外面晃悠的时间越来越长，直到有一天，在被猫妈试图抚摸未果的
美猫！
【在 R******0 的大作中提到】
: 自上周一与猫爸猫妈亲密接触以后，奶昔饮食正常，情绪稳(fanfu)定(wuchang)，曾经
: 被当成砂盆的南瓜窝也变成了好地方~~
: 每天晚饭时间，可乐和雪碧被邀请到包厢享受大餐，奶昔闻着俩陌生喵的味道淡去，小
: 心地踱到门外，四处张望
: 坐得好累，趴一会，翻过来，又翻过去，似乎真的没有什么危险了
: 这个黑黑的大盒子是什么东西，上去看看
: 啊，这里看起来很隐蔽，是个休息的好地方
: 没人看我吧，我去那边开阔地带转转
: 不好！有人来了！赶紧找机会回去！
: 就这样，奶昔每天在外面晃悠的时间越来越长，直到有一天，在被猫妈试图抚摸未果的
P*L
40 楼
这样做是最好的，但是还得找最大公约数，容易超时过不了 oj。
【在 g*********e 的大作中提到】
: 如果坐标是整数的话，斜率都是有理数。可以存pair
【在 g*********e 的大作中提到】
: 如果坐标是整数的话，斜率都是有理数。可以存pair
z*e
41 楼
赞组图！很有real journalism的味道！
h*e
42 楼
要自己加hash function的，我写了一个总算过了编译了
namespace std {
template <>
struct hash >
{
typedef std::size_t result_type;
result_type operator()(const pair & t) const
{
return t.first * 1000003 + t.second;
}
};
}
备注 (不过似乎不太好~~ 似乎 hash值 溢出了~~~ )但是也过了oj了。
有没有人写过这个hash, 这个似乎是c++ 0x/11新标准 ~~这个hash函数该怎么写才能
写得简单少冲突而又 不越界呢~~
gcd非常少的代码的。就是辗转相除一行代码就行。
【在 P*******L 的大作中提到】
: 这样做是最好的，但是还得找最大公约数，容易超时过不了 oj。
namespace std {
template <>
struct hash
{
typedef std::size_t result_type;
result_type operator()(const pair
{
return t.first * 1000003 + t.second;
}
};
}
备注 (不过似乎不太好~~ 似乎 hash值 溢出了~~~ )但是也过了oj了。
有没有人写过这个hash, 这个似乎是c++ 0x/11新标准 ~~这个hash函数该怎么写才能
写得简单少冲突而又 不越界呢~~
gcd非常少的代码的。就是辗转相除一行代码就行。
【在 P*******L 的大作中提到】
: 这样做是最好的，但是还得找最大公约数，容易超时过不了 oj。
R*0
43 楼
是呀，典型的defensive aggression。。。
就在我被攻击之前的半小时左右，我们就在玩激光笔和大鸟，她会去扑，但比较缓慢，
估计还是有所保留，比如只往房间的一个方向扑，如果激光笔指到另一边就不去了。
现在看她这么出来逛游，我是真的有心理阴影，她一离我不到两米，我就紧张地要躲，
尤其是她快速向我靠近的时候。。。她也怕我，一有动静就立即努力贴着地往自己的房
间奔
【在 c******y 的大作中提到】
: 奶昔尾巴还垂着 这娃戒心有多重啊。。。。。。
: 碰玩具不？喜欢catnip不？大鸟玩不玩？
就在我被攻击之前的半小时左右，我们就在玩激光笔和大鸟，她会去扑，但比较缓慢，
估计还是有所保留，比如只往房间的一个方向扑，如果激光笔指到另一边就不去了。
现在看她这么出来逛游，我是真的有心理阴影，她一离我不到两米，我就紧张地要躲，
尤其是她快速向我靠近的时候。。。她也怕我，一有动静就立即努力贴着地往自己的房
间奔
【在 c******y 的大作中提到】
: 奶昔尾巴还垂着 这娃戒心有多重啊。。。。。。
: 碰玩具不？喜欢catnip不？大鸟玩不玩？
g*e
44 楼
set, int>
这个直接就可以用啊
想过leetcode的话用floating的比较就足够了，但google面试的时候我用floating的斜
率 Interviewer就不让过
这个直接就可以用啊
想过leetcode的话用floating的比较就足够了，但google面试的时候我用floating的斜
率 Interviewer就不让过
R*0
45 楼
原来跟熟悉的人一起换环境也会这样啊，那我就再多加点耐心吧
【在 g*****y 的大作中提到】
: 有的猫猫很需要耐心啊。。 我养了10年的猫，搬到新家也是藏床底下几个月。。。。
: 基本上我门回家才出来转悠一小会儿。。
【在 g*****y 的大作中提到】
: 有的猫猫很需要耐心啊。。 我养了10年的猫，搬到新家也是藏床底下几个月。。。。
: 基本上我门回家才出来转悠一小会儿。。
h*e
46 楼
google 是要求pair 做斜率么？
google是要求精确在一条直线上， 还是要求近似的可以有些误差的点也算一条线阿。
请大牛给细说说g关于这道题的要求阿。
【在 g*********e 的大作中提到】
: set, int>
: 这个直接就可以用啊
: 想过leetcode的话用floating的比较就足够了，但google面试的时候我用floating的斜
: 率 Interviewer就不让过
google是要求精确在一条直线上， 还是要求近似的可以有些误差的点也算一条线阿。
请大牛给细说说g关于这道题的要求阿。
【在 g*********e 的大作中提到】
: set
: 这个直接就可以用啊
: 想过leetcode的话用floating的比较就足够了，但google面试的时候我用floating的斜
: 率 Interviewer就不让过
R*0
47 楼
希望这个过程不要太久，现在她还只觉得那个小卫生间是她自己最舒服最安全的地方
【在 w****2 的大作中提到】
: 哈哈，小美妞出来了，慢慢地会占领每一间房
【在 w****2 的大作中提到】
: 哈哈，小美妞出来了，慢慢地会占领每一间房
g*e
48 楼
要精确的 不能用epsilon这样去比。不过也看面试官吧
【在 h*******e 的大作中提到】
: google 是要求pair
: google是要求精确在一条直线上， 还是要求近似的可以有些误差的点也算一条线阿。
: 请大牛给细说说g关于这道题的要求阿。
Y*Y
49 楼
奶昔看来是狠角色啊！
h*e
50 楼
恩恩，多谢了。
【在 g*********e 的大作中提到】
:
: 要精确的 不能用epsilon这样去比。不过也看面试官吧
【在 g*********e 的大作中提到】
:
: 要精确的 不能用epsilon这样去比。不过也看面试官吧
R*0
51 楼
是呀，后妈很过分~~当时查了一些关于aggressive猫猫的应对，很多就是建议先让猫猫
冷静下来，减少接触，适当饥饿，让她重新把我们跟美好的食物联系起来~~
【在 I********e 的大作中提到】
: 出了口气马上被关三天，LOL..
: 美猫！
冷静下来，减少接触，适当饥饿，让她重新把我们跟美好的食物联系起来~~
【在 I********e 的大作中提到】
: 出了口气马上被关三天，LOL..
: 美猫！
f*5
52 楼
有一个思路不知道对不对，用unordered_map
斜率可以表示成循环小数, 比如5/6=0.8(3)， 还没在leetcode上试，不知道能不能过
【在 h*******e 的大作中提到】
: 要自己加hash function的，我写了一个总算过了编译了
: namespace std {
: template <>
: struct hash
: {
: typedef std::size_t result_type;
: result_type operator()(const pair
: {
: return t.first * 1000003 + t.second;
: }
R*0
53 楼
哈哈，虽然不敢当，但还是让后妈再乐一阵吧~~
【在 z*****e 的大作中提到】
: 赞组图！很有real journalism的味道！
【在 z*****e 的大作中提到】
: 赞组图！很有real journalism的味道！
s*5
54 楼
use hash of hash: unordered_map >
【在 h*******e 的大作中提到】
: 如果是pair作为 key 的话自定义的hash 函数一般怎么写
: 在 c++ unordered_set, int> 大牛给讲一下哦。
【在 h*******e 的大作中提到】
: 如果是pair作为 key 的话自定义的hash 函数一般怎么写
: 在 c++ unordered_set
R*0
55 楼
正是，不能等闲视之啊
【在 Y******Y 的大作中提到】
: 奶昔看来是狠角色啊！
【在 Y******Y 的大作中提到】
: 奶昔看来是狠角色啊！
h*e
56 楼
我之前用的map 把 pair 的两个 int 变成string 中间加上
" "然后再加上 string 变成一个长string 你的方法也是对的一个 无理数唯一对应
一个非循环，和循环部分的组合。就是这个求循环节的过程比较麻烦了，估计你数学功
底很好，可以很快求出来。
【在 f*******5 的大作中提到】
:
: 有一个思路不知道对不对，用unordered_map, 因为点坐标是整数，所以
: 斜率可以表示成循环小数, 比如5/6=0.8(3)， 还没在leetcode上试，不知道能不能过
" "然后再加上 string 变成一个长string 你的方法也是对的一个 无理数唯一对应
一个非循环，和循环部分的组合。就是这个求循环节的过程比较麻烦了，估计你数学功
底很好，可以很快求出来。
【在 f*******5 的大作中提到】
:
: 有一个思路不知道对不对，用unordered_map
: 斜率可以表示成循环小数, 比如5/6=0.8(3)， 还没在leetcode上试，不知道能不能过
c*y
57 楼
肯出来转圈巡视总是个不小的进步！
猫奴不好当诶。。
唉只委屈了可乐雪碧 他俩招谁惹谁了就被限制活动范围了。。。
【在 R******0 的大作中提到】
: 是呀，典型的defensive aggression。。。
: 就在我被攻击之前的半小时左右，我们就在玩激光笔和大鸟，她会去扑，但比较缓慢，
: 估计还是有所保留，比如只往房间的一个方向扑，如果激光笔指到另一边就不去了。
: 现在看她这么出来逛游，我是真的有心理阴影，她一离我不到两米，我就紧张地要躲，
: 尤其是她快速向我靠近的时候。。。她也怕我，一有动静就立即努力贴着地往自己的房
: 间奔
猫奴不好当诶。。
唉只委屈了可乐雪碧 他俩招谁惹谁了就被限制活动范围了。。。
【在 R******0 的大作中提到】
: 是呀，典型的defensive aggression。。。
: 就在我被攻击之前的半小时左右，我们就在玩激光笔和大鸟，她会去扑，但比较缓慢，
: 估计还是有所保留，比如只往房间的一个方向扑，如果激光笔指到另一边就不去了。
: 现在看她这么出来逛游，我是真的有心理阴影，她一离我不到两米，我就紧张地要躲，
: 尤其是她快速向我靠近的时候。。。她也怕我，一有动静就立即努力贴着地往自己的房
: 间奔
h*e
58 楼
是不是key value类型写反了，而且复杂的类型做key比较麻烦在leetcode 定义就不可
以，vs2010定义没问题，但是往里面map[key]= val 赋值时候就编译不过了。
【在 s***5 的大作中提到】
: use hash of hash: unordered_map >
以，vs2010定义没问题，但是往里面map[key]= val 赋值时候就编译不过了。
【在 s***5 的大作中提到】
: use hash of hash: unordered_map
R*0
59 楼
是，肯出来已经不错了，最开始是开着门好几个小时也蹲在池子底下一动不动。可乐雪
碧的话，希望他们足够没心没肺吧，或者他们已经互相商量过也理解是怎么回事了，哈
哈~一天奶昔顶多出来两三个小时，应该还好。最希望的还是他们能尽早结束隔离啊
【在 c******y 的大作中提到】
: 肯出来转圈巡视总是个不小的进步！
: 猫奴不好当诶。。
: 唉只委屈了可乐雪碧 他俩招谁惹谁了就被限制活动范围了。。。
碧的话，希望他们足够没心没肺吧，或者他们已经互相商量过也理解是怎么回事了，哈
哈~一天奶昔顶多出来两三个小时，应该还好。最希望的还是他们能尽早结束隔离啊
【在 c******y 的大作中提到】
: 肯出来转圈巡视总是个不小的进步！
: 猫奴不好当诶。。
: 唉只委屈了可乐雪碧 他俩招谁惹谁了就被限制活动范围了。。。
f*5
60 楼
有个Google面试题是求整数除法的循环，是不断用余数做被除数，用一个bool arr[10]
记录被除数，当前被除数如果见过就表示循环
【在 h*******e 的大作中提到】
: 是不是key value类型写反了，而且复杂的类型做key比较麻烦在leetcode 定义就不可
: 以，vs2010定义没问题，但是往里面map[key]= val 赋值时候就编译不过了。
k*e
61 楼
美貌的一般脾气都有点大～
你不理她几天估计她就会主动靠近你啦
【在 R******0 的大作中提到】
: 自上周一与猫爸猫妈亲密接触以后，奶昔饮食正常，情绪稳(fanfu)定(wuchang)，曾经
: 被当成砂盆的南瓜窝也变成了好地方~~
: 每天晚饭时间，可乐和雪碧被邀请到包厢享受大餐，奶昔闻着俩陌生喵的味道淡去，小
: 心地踱到门外，四处张望
: 坐得好累，趴一会，翻过来，又翻过去，似乎真的没有什么危险了
: 这个黑黑的大盒子是什么东西，上去看看
: 啊，这里看起来很隐蔽，是个休息的好地方
: 没人看我吧，我去那边开阔地带转转
: 不好！有人来了！赶紧找机会回去！
: 就这样，奶昔每天在外面晃悠的时间越来越长，直到有一天，在被猫妈试图抚摸未果的
你不理她几天估计她就会主动靠近你啦
【在 R******0 的大作中提到】
: 自上周一与猫爸猫妈亲密接触以后，奶昔饮食正常，情绪稳(fanfu)定(wuchang)，曾经
: 被当成砂盆的南瓜窝也变成了好地方~~
: 每天晚饭时间，可乐和雪碧被邀请到包厢享受大餐，奶昔闻着俩陌生喵的味道淡去，小
: 心地踱到门外，四处张望
: 坐得好累，趴一会，翻过来，又翻过去，似乎真的没有什么危险了
: 这个黑黑的大盒子是什么东西，上去看看
: 啊，这里看起来很隐蔽，是个休息的好地方
: 没人看我吧，我去那边开阔地带转转
: 不好！有人来了！赶紧找机会回去！
: 就这样，奶昔每天在外面晃悠的时间越来越长，直到有一天，在被猫妈试图抚摸未果的
h*e
62 楼
呵呵，估计写得好能小impress面试官一下，本想出一道难题，没成想面试者一口气完
成了两道难题。
10]
【在 f*******5 的大作中提到】
:
: 有个Google面试题是求整数除法的循环，是不断用余数做被除数，用一个bool arr[10]
: 记录被除数，当前被除数如果见过就表示循环
成了两道难题。
10]
【在 f*******5 的大作中提到】
:
: 有个Google面试题是求整数除法的循环，是不断用余数做被除数，用一个bool arr[10]
: 记录被除数，当前被除数如果见过就表示循环
c*y
63 楼
他们互相安慰希望没事
道路曲折了点儿但前途一定很光明啦！
也给个大馅儿包子安慰安慰
【在 R******0 的大作中提到】
: 是，肯出来已经不错了，最开始是开着门好几个小时也蹲在池子底下一动不动。可乐雪
: 碧的话，希望他们足够没心没肺吧，或者他们已经互相商量过也理解是怎么回事了，哈
: 哈~一天奶昔顶多出来两三个小时，应该还好。最希望的还是他们能尽早结束隔离啊
道路曲折了点儿但前途一定很光明啦！
也给个大馅儿包子安慰安慰
【在 R******0 的大作中提到】
: 是，肯出来已经不错了，最开始是开着门好几个小时也蹲在池子底下一动不动。可乐雪
: 碧的话，希望他们足够没心没肺吧，或者他们已经互相商量过也理解是怎么回事了，哈
: 哈~一天奶昔顶多出来两三个小时，应该还好。最希望的还是他们能尽早结束隔离啊
y*n
64 楼
那Sqrt 那个题可以用epsilon吗？
【在 g*********e 的大作中提到】
:
: 要精确的 不能用epsilon这样去比。不过也看面试官吧
【在 g*********e 的大作中提到】
:
: 要精确的 不能用epsilon这样去比。不过也看面试官吧
N*t
65 楼
终于出来了阿，不错不错，有进步～
奶昔在以前的家里是不是从很小开始独猫养的？我见过俩狠角色都是这样，玛雅，压力
山大，赞mm勇气可嘉
奶昔在以前的家里是不是从很小开始独猫养的？我见过俩狠角色都是这样，玛雅，压力
山大，赞mm勇气可嘉
g*e
66 楼
记得数学的算cross product
不记得的斜率公式转换一下变乘法，其实就是叉乘
【在 g*********e 的大作中提到】
: set, int>
: 这个直接就可以用啊
: 想过leetcode的话用floating的比较就足够了，但google面试的时候我用floating的斜
: 率 Interviewer就不让过
不记得的斜率公式转换一下变乘法，其实就是叉乘
【在 g*********e 的大作中提到】
: set
: 这个直接就可以用啊
: 想过leetcode的话用floating的比较就足够了，但google面试的时候我用floating的斜
: 率 Interviewer就不让过
R*0
67 楼
还真是这样的，关了三天小黑屋以后感觉奶昔更乖了，开门也不hiss了，反而是很温柔
喵喵地叫，还疑似翻肚皮，隔着门叫她名字，她也喵喵地回应，不知道是不是真的想亲
近，还是跟她的外表一样容易蛊惑人啊~~
【在 k*******e 的大作中提到】
: 美貌的一般脾气都有点大～
: 你不理她几天估计她就会主动靠近你啦
喵喵地叫，还疑似翻肚皮，隔着门叫她名字，她也喵喵地回应，不知道是不是真的想亲
近，还是跟她的外表一样容易蛊惑人啊~~
【在 k*******e 的大作中提到】
: 美貌的一般脾气都有点大～
: 你不理她几天估计她就会主动靠近你啦
g*e
68 楼
表示成2/7=0.[285714]
10]
【在 f*******5 的大作中提到】
:
: 有个Google面试题是求整数除法的循环，是不断用余数做被除数，用一个bool arr[10]
: 记录被除数，当前被除数如果见过就表示循环
10]
【在 f*******5 的大作中提到】
:
: 有个Google面试题是求整数除法的循环，是不断用余数做被除数，用一个bool arr[10]
: 记录被除数，当前被除数如果见过就表示循环
R*0
69 楼
谢谢猫糖~~大包子真好吃~~~
【在 c******y 的大作中提到】
: 他们互相安慰希望没事
: 道路曲折了点儿但前途一定很光明啦！
: 也给个大馅儿包子安慰安慰
【在 c******y 的大作中提到】
: 他们互相安慰希望没事
: 道路曲折了点儿但前途一定很光明啦！
: 也给个大馅儿包子安慰安慰
g*e
70 楼
可以
【在 y***n 的大作中提到】
: 那Sqrt 那个题可以用epsilon吗？
【在 y***n 的大作中提到】
: 那Sqrt 那个题可以用epsilon吗？
R*0
71 楼
没错没错，就是四周大从shelter去了前主人家，9个月被我领回来，一直是一只喵在家
，只有隔壁一只outdoor的壮男brown tabby时不时地来看她，我们去领奶昔的时候还见
到这个大男猫在门口守着，听说也没有正式接触过，奶昔一见对方就躲进里屋。
我们全家都是被那两张照片迷失了心智啊，没想到独猫rehome是这个样子的，嘿嘿~~你
见过的那俩狠角色是什么情况啊
【在 N******t 的大作中提到】
: 终于出来了阿，不错不错，有进步～
: 奶昔在以前的家里是不是从很小开始独猫养的？我见过俩狠角色都是这样，玛雅，压力
: 山大，赞mm勇气可嘉
，只有隔壁一只outdoor的壮男brown tabby时不时地来看她，我们去领奶昔的时候还见
到这个大男猫在门口守着，听说也没有正式接触过，奶昔一见对方就躲进里屋。
我们全家都是被那两张照片迷失了心智啊，没想到独猫rehome是这个样子的，嘿嘿~~你
见过的那俩狠角色是什么情况啊
【在 N******t 的大作中提到】
: 终于出来了阿，不错不错，有进步～
: 奶昔在以前的家里是不是从很小开始独猫养的？我见过俩狠角色都是这样，玛雅，压力
: 山大，赞mm勇气可嘉
y*n
72 楼
你搞得那么细，以后可以写一本书。每个题写：
A. 基本解法。
A-1. Google解法。
A-2。Facebook 解法。
A-3。 Linkedin解法。
【在 h*******e 的大作中提到】
: google 是要求pair 做斜率么？
: google是要求精确在一条直线上， 还是要求近似的可以有些误差的点也算一条线阿。
: 请大牛给细说说g关于这道题的要求阿。
A. 基本解法。
A-1. Google解法。
A-2。Facebook 解法。
A-3。 Linkedin解法。
【在 h*******e 的大作中提到】
: google 是要求pair
: google是要求精确在一条直线上， 还是要求近似的可以有些误差的点也算一条线阿。
: 请大牛给细说说g关于这道题的要求阿。
N*t
73 楼
我见过的那俩，一个我cat sit过N次包括过夜，一个在我家呆了好几天，俩我都没摸到
过一根毛阿，在他们附近走路都是拿东西挡着腿 T_T 我承认我心理脆弱
不过他们跟各自的妈都是亲的不得了，mm应该很快会守得云开见月明～
【在 R******0 的大作中提到】
: 没错没错，就是四周大从shelter去了前主人家，9个月被我领回来，一直是一只喵在家
: ，只有隔壁一只outdoor的壮男brown tabby时不时地来看她，我们去领奶昔的时候还见
: 到这个大男猫在门口守着，听说也没有正式接触过，奶昔一见对方就躲进里屋。
: 我们全家都是被那两张照片迷失了心智啊，没想到独猫rehome是这个样子的，嘿嘿~~你
: 见过的那俩狠角色是什么情况啊
过一根毛阿，在他们附近走路都是拿东西挡着腿 T_T 我承认我心理脆弱
不过他们跟各自的妈都是亲的不得了，mm应该很快会守得云开见月明～
【在 R******0 的大作中提到】
: 没错没错，就是四周大从shelter去了前主人家，9个月被我领回来，一直是一只喵在家
: ，只有隔壁一只outdoor的壮男brown tabby时不时地来看她，我们去领奶昔的时候还见
: 到这个大男猫在门口守着，听说也没有正式接触过，奶昔一见对方就躲进里屋。
: 我们全家都是被那两张照片迷失了心智啊，没想到独猫rehome是这个样子的，嘿嘿~~你
: 见过的那俩狠角色是什么情况啊
h*e
74 楼
你多做些计算几何题就知道了，计算几何差一点就差很多， 比如三点共线的标准方法
就是叉乘面积近似为0，近似斜率做就引进边的长度误差，计算几何在严格一点的oj上都
是差之毫厘，失之千里的，过了leetcode的 oj的做法很多不一定就一定无懈可击，往
往面试难得不是原题，而是是要求改一点，比如这道题之前c++ 不支持 unordered_set
的时候就看过这道题，那要高效算法就只能手动写链表hash table实现hash~~ 这道题
glowinglake 的 follow up 也不是那么简单说海量数据情况下应该怎么变我还没细想
。
by the way 关于sqrt 那道题 虽然可以用 epsilon但是有不用 epsilon的精确解法，
不知道你能不能想出来。
【在 y***n 的大作中提到】
: 你搞得那么细，以后可以写一本书。每个题写：
: A. 基本解法。
: A-1. Google解法。
: A-2。Facebook 解法。
: A-3。 Linkedin解法。
就是叉乘面积近似为0，近似斜率做就引进边的长度误差，计算几何在严格一点的oj上都
是差之毫厘，失之千里的，过了leetcode的 oj的做法很多不一定就一定无懈可击，往
往面试难得不是原题，而是是要求改一点，比如这道题之前c++ 不支持 unordered_set
的时候就看过这道题，那要高效算法就只能手动写链表hash table实现hash~~ 这道题
glowinglake 的 follow up 也不是那么简单说海量数据情况下应该怎么变我还没细想
。
by the way 关于sqrt 那道题 虽然可以用 epsilon但是有不用 epsilon的精确解法，
不知道你能不能想出来。
【在 y***n 的大作中提到】
: 你搞得那么细，以后可以写一本书。每个题写：
: A. 基本解法。
: A-1. Google解法。
: A-2。Facebook 解法。
: A-3。 Linkedin解法。
z*e
75 楼
别介~猫猫心思敏感，看你躲她，说不定更 confused了呢~这时一定要拿出正牌猫奴的
架势把她给镇住。嗯~
【在 R******0 的大作中提到】
: 是呀，典型的defensive aggression。。。
: 就在我被攻击之前的半小时左右，我们就在玩激光笔和大鸟，她会去扑，但比较缓慢，
: 估计还是有所保留，比如只往房间的一个方向扑，如果激光笔指到另一边就不去了。
: 现在看她这么出来逛游，我是真的有心理阴影，她一离我不到两米，我就紧张地要躲，
: 尤其是她快速向我靠近的时候。。。她也怕我，一有动静就立即努力贴着地往自己的房
: 间奔
架势把她给镇住。嗯~
【在 R******0 的大作中提到】
: 是呀，典型的defensive aggression。。。
: 就在我被攻击之前的半小时左右，我们就在玩激光笔和大鸟，她会去扑，但比较缓慢，
: 估计还是有所保留，比如只往房间的一个方向扑，如果激光笔指到另一边就不去了。
: 现在看她这么出来逛游，我是真的有心理阴影，她一离我不到两米，我就紧张地要躲，
: 尤其是她快速向我靠近的时候。。。她也怕我，一有动静就立即努力贴着地往自己的房
: 间奔
h*t
76 楼
这个能再多解释一下吗？
【在 g**e 的大作中提到】
: 记得数学的算cross product
: 不记得的斜率公式转换一下变乘法，其实就是叉乘
K*a
77 楼
拿东西挡着腿。。。。笑S了
【在 N******t 的大作中提到】
: 我见过的那俩，一个我cat sit过N次包括过夜，一个在我家呆了好几天，俩我都没摸到
: 过一根毛阿，在他们附近走路都是拿东西挡着腿 T_T 我承认我心理脆弱
: 不过他们跟各自的妈都是亲的不得了，mm应该很快会守得云开见月明～
【在 N******t 的大作中提到】
: 我见过的那俩，一个我cat sit过N次包括过夜，一个在我家呆了好几天，俩我都没摸到
: 过一根毛阿，在他们附近走路都是拿东西挡着腿 T_T 我承认我心理脆弱
: 不过他们跟各自的妈都是亲的不得了，mm应该很快会守得云开见月明～
h*t
78 楼
弱问一句：为什么只存 slope作为key呢， 不需要存和 y轴交点吗？
【在 h*******e 的大作中提到】
: 如果是pair作为 key 的话自定义的hash 函数一般怎么写
: 在 c++ unordered_set
R*0
79 楼
“在他们附近走路都是拿东西挡着腿”，我现在差不多就想这样，太理解了~~希望奶昔
早点认我作亲妈~~
【在 N******t 的大作中提到】
: 我见过的那俩，一个我cat sit过N次包括过夜，一个在我家呆了好几天，俩我都没摸到
: 过一根毛阿，在他们附近走路都是拿东西挡着腿 T_T 我承认我心理脆弱
: 不过他们跟各自的妈都是亲的不得了，mm应该很快会守得云开见月明～
早点认我作亲妈~~
【在 N******t 的大作中提到】
: 我见过的那俩，一个我cat sit过N次包括过夜，一个在我家呆了好几天，俩我都没摸到
: 过一根毛阿，在他们附近走路都是拿东西挡着腿 T_T 我承认我心理脆弱
: 不过他们跟各自的妈都是亲的不得了，mm应该很快会守得云开见月明～
h*e
80 楼
不同的2点确定一条直线，确定一个直线方程，确定一斜率。
【在 h****t 的大作中提到】
:
: 弱问一句：为什么只存 slope作为key呢， 不需要存和 y轴交点吗？
【在 h****t 的大作中提到】
:
: 弱问一句：为什么只存 slope作为key呢， 不需要存和 y轴交点吗？
R*0
81 楼
好难啊~这真的需要无比强大的心理~~
短期内我就先多穿点好了，再拿出正牌猫奴的架势，哈！
【在 z*****e 的大作中提到】
: 别介~猫猫心思敏感，看你躲她，说不定更 confused了呢~这时一定要拿出正牌猫奴的
: 架势把她给镇住。嗯~
短期内我就先多穿点好了，再拿出正牌猫奴的架势，哈！
【在 z*****e 的大作中提到】
: 别介~猫猫心思敏感，看你躲她，说不定更 confused了呢~这时一定要拿出正牌猫奴的
: 架势把她给镇住。嗯~
h*t
82 楼
我的意思是 会存在2条不同的平行直线（相同斜率）。
只存斜率无法区分这2条不同直线。
【在 h*******e 的大作中提到】
: 不同的2点确定一条直线，确定一个直线方程，确定一斜率。
只存斜率无法区分这2条不同直线。
【在 h*******e 的大作中提到】
: 不同的2点确定一条直线，确定一个直线方程，确定一斜率。
R*0
83 楼
真事啊，照片里那个红灰相见的beanbag chair就经常被我们拿来挡着。。。
【在 K***a 的大作中提到】
: 拿东西挡着腿。。。。笑S了
【在 K***a 的大作中提到】
: 拿东西挡着腿。。。。笑S了
h*e
84 楼
我感觉你对这道题的总体思路还没有概念，为了不spoil你刷题的乐趣，你可以尝试思
考并且做一下leetcode第三题。max points on a line.
【在 h****t 的大作中提到】
: 我的意思是 会存在2条不同的平行直线（相同斜率）。
: 只存斜率无法区分这2条不同直线。
考并且做一下leetcode第三题。max points on a line.
【在 h****t 的大作中提到】
: 我的意思是 会存在2条不同的平行直线（相同斜率）。
: 只存斜率无法区分这2条不同直线。
H*o
85 楼
小美女好有性格啊，这么看起来lz我碰到的猫脾气都很好很好啊。。。。
有朋友家的猫放我家寄养。来了以后就四处视察，见到我的猫炸毛也无所谓。看到人就
翻肚皮求吃的。。。。
有我家二毛，来了以后隔离在厕所，听到我的声音，隔着厕所门都能听见她打呼噜的咕
咕声音。见到我亲的就像见到了娘。只要放出厕所，立刻上蹿下跳。把家里大猫搞得不
能安生。。。
有朋友家的猫放我家寄养。来了以后就四处视察，见到我的猫炸毛也无所谓。看到人就
翻肚皮求吃的。。。。
有我家二毛，来了以后隔离在厕所，听到我的声音，隔着厕所门都能听见她打呼噜的咕
咕声音。见到我亲的就像见到了娘。只要放出厕所，立刻上蹿下跳。把家里大猫搞得不
能安生。。。
h*t
86 楼
不知道你的感觉从何而来。
2年前面世时就被问过这题并且答案通过。leetcode什么的其它不多说了，没刷过的人
现在不多了。
"总体思路还没有概念"，嘿嘿，嘿嘿。我一笑而过。
【在 h*******e 的大作中提到】
: 我感觉你对这道题的总体思路还没有概念，为了不spoil你刷题的乐趣，你可以尝试思
: 考并且做一下leetcode第三题。max points on a line.
2年前面世时就被问过这题并且答案通过。leetcode什么的其它不多说了，没刷过的人
现在不多了。
"总体思路还没有概念"，嘿嘿，嘿嘿。我一笑而过。
【在 h*******e 的大作中提到】
: 我感觉你对这道题的总体思路还没有概念，为了不spoil你刷题的乐趣，你可以尝试思
: 考并且做一下leetcode第三题。max points on a line.
b*e
87 楼
指甲剪掉强抱是王道，俺最近就收拾了一只，三两天就主动爬上肚子了
【在 R******0 的大作中提到】
: “在他们附近走路都是拿东西挡着腿”，我现在差不多就想这样，太理解了~~希望奶昔
: 早点认我作亲妈~~
【在 R******0 的大作中提到】
: “在他们附近走路都是拿东西挡着腿”，我现在差不多就想这样，太理解了~~希望奶昔
: 早点认我作亲妈~~
y*n
88 楼
他应该不是用 slope作为key呢
【在 h****t 的大作中提到】
: 不知道你的感觉从何而来。
: 2年前面世时就被问过这题并且答案通过。leetcode什么的其它不多说了，没刷过的人
: 现在不多了。
: "总体思路还没有概念"，嘿嘿，嘿嘿。我一笑而过。
【在 h****t 的大作中提到】
: 不知道你的感觉从何而来。
: 2年前面世时就被问过这题并且答案通过。leetcode什么的其它不多说了，没刷过的人
: 现在不多了。
: "总体思路还没有概念"，嘿嘿，嘿嘿。我一笑而过。
N*t
89 楼
真的会突然尖叫着冲上来攻击阿。。。吓死我的小心肝了
【在 K***a 的大作中提到】
: 拿东西挡着腿。。。。笑S了
【在 K***a 的大作中提到】
: 拿东西挡着腿。。。。笑S了
h*e
90 楼
哦那就是你刷题和我们大多数人的思路很不同哦，不妨你也介绍一下你的做法，大家开
阔思路哦。
我们是算每点和其他点的斜率，用斜率为key做hashmap, 看和本点相连的其他点落在
每个斜率内的有几个。 然后枚举这个轴心点 这样算法复杂度O(N*N)
我们现在都是用斜率作key 整个帖子纠结的是斜率怎么存和相应的精确度的问题，看
你说似乎不是用斜率做key,
所以开始还以为你没做过呢。
【在 h****t 的大作中提到】
: 不知道你的感觉从何而来。
: 2年前面世时就被问过这题并且答案通过。leetcode什么的其它不多说了，没刷过的人
: 现在不多了。
: "总体思路还没有概念"，嘿嘿，嘿嘿。我一笑而过。
阔思路哦。
我们是算每点和其他点的斜率，用斜率为key做hashmap, 看和本点相连的其他点落在
每个斜率内的有几个。 然后枚举这个轴心点 这样算法复杂度O(N*N)
我们现在都是用斜率作key 整个帖子纠结的是斜率怎么存和相应的精确度的问题，看
你说似乎不是用斜率做key,
所以开始还以为你没做过呢。
【在 h****t 的大作中提到】
: 不知道你的感觉从何而来。
: 2年前面世时就被问过这题并且答案通过。leetcode什么的其它不多说了，没刷过的人
: 现在不多了。
: "总体思路还没有概念"，嘿嘿，嘿嘿。我一笑而过。
B*A
91 楼
美女！
i*s
92 楼
忍不住替habbit说一句，如果枚举所有点，并且每次内循环前用新的hashmap的话，可
以只存斜率，因为此时之前一点已经固定(外层循环确定起始点)，所以可以用斜率做
key。但是如果hashmap不是每次内循环前创建，而是在双重循序前创建，那么截距是一
定要的，光slope不够。还有这道题用slope有精度问题，
消除方法最简单就是换个直线表示方式，用Ax+By+C = 0。其中A, B和C都是整数，每两
个点构成的直线都这样表示，注意用gcd法保证A,B和C没有公约数，并且保证符号相
同(可以假设A永远是正)。而且这道题最大的trick是如何处理重复的点，一般没做过的
第一次做不一定想得到好办法。总体看之前的讨论无语了，跳出来说几句。
【在 h*******e 的大作中提到】
: 哦那就是你刷题和我们大多数人的思路很不同哦，不妨你也介绍一下你的做法，大家开
: 阔思路哦。
: 我们是算每点和其他点的斜率，用斜率为key做hashmap, 看和本点相连的其他点落在
: 每个斜率内的有几个。 然后枚举这个轴心点 这样算法复杂度O(N*N)
: 我们现在都是用斜率作key 整个帖子纠结的是斜率怎么存和相应的精确度的问题，看
: 你说似乎不是用斜率做key,
: 所以开始还以为你没做过呢。
以只存斜率，因为此时之前一点已经固定(外层循环确定起始点)，所以可以用斜率做
key。但是如果hashmap不是每次内循环前创建，而是在双重循序前创建，那么截距是一
定要的，光slope不够。还有这道题用slope有精度问题，
消除方法最简单就是换个直线表示方式，用Ax+By+C = 0。其中A, B和C都是整数，每两
个点构成的直线都这样表示，注意用gcd法保证A,B和C没有公约数，并且保证符号相
同(可以假设A永远是正)。而且这道题最大的trick是如何处理重复的点，一般没做过的
第一次做不一定想得到好办法。总体看之前的讨论无语了，跳出来说几句。
【在 h*******e 的大作中提到】
: 哦那就是你刷题和我们大多数人的思路很不同哦，不妨你也介绍一下你的做法，大家开
: 阔思路哦。
: 我们是算每点和其他点的斜率，用斜率为key做hashmap, 看和本点相连的其他点落在
: 每个斜率内的有几个。 然后枚举这个轴心点 这样算法复杂度O(N*N)
: 我们现在都是用斜率作key 整个帖子纠结的是斜率怎么存和相应的精确度的问题，看
: 你说似乎不是用斜率做key,
: 所以开始还以为你没做过呢。
L*3
93 楼
哈哈哈，美女果然有脾气！
【在 R******0 的大作中提到】
: “在他们附近走路都是拿东西挡着腿”，我现在差不多就想这样，太理解了~~希望奶昔
: 早点认我作亲妈~~
【在 R******0 的大作中提到】
: “在他们附近走路都是拿东西挡着腿”，我现在差不多就想这样，太理解了~~希望奶昔
: 早点认我作亲妈~~
h*e
94 楼
namespace std {
template <>
struct hash >
{
typedef std::size_t result_type;
result_type operator()(const pair & t) const
{ return ((long)t.first * 1000003 + t.second )& (((long)1<<32 ) - 1);
}
};
}
class Solution {
public:
// suppose no two points are the same
int gcd(int a, int b)
{ return !b? a: gcd(b, a %b); }
pair getK(vector & points, int pointI, int pointJ)
{
int x1 = points[pointI].x, y1 = points[pointI].y,
x2 = points[pointJ].x, y2 = points[pointJ].y;
int diffy = y1 - y2, diffx = x1 - x2;
if(diffy == 0 || diffx == 0)
{
if(diffy == 0) diffx = 1;
if(diffx == 0) diffy = 1;
return make_pair(diffy, diffx);
}
if(diffy < 0)
{
diffy = -diffy;
diffx = -diffx;
}
int gcdVal = gcd(abs(diffy), abs(diffx));
return make_pair(diffy/gcdVal, diffx/gcdVal);
}
bool samePoint(vector & points, int pointI, int pointJ)
{ return points[pointI].x == points[pointJ].x && points[pointI].y ==
points[pointJ].y; }
/*
string intToStr(int val)
{
if(!val) return "0";
string str = "";
while(val)
{
str += val %10 + '0';
val /= 10;
}
reverse(str.begin(), str.end());
return str;
}
string pairToStr(pair & p)
{ return intToStr(p.first) + " " + intToStr(p.second);}
＊/
int maxPoints(vector &points) {
unordered_map, int > map;
int maxPoint = 0;
for(int pointI = 0; pointI < points.size(); ++ pointI)
{
map.clear();
int sameCnt = 1, diffMax = 0;
for(int pointJ = 0; pointJ < points.size(); ++ pointJ)
{
if(pointI == pointJ) continue;
if(samePoint(points, pointI, pointJ))
{
++ sameCnt;
continue;
}
pair kval = getK(points, pointI, pointJ);
if(map.find(kval) == map.end())
map[kval] = 1;
else
++map[kval];
diffMax = max(diffMax, map[kval]);
}
maxPoint = max(maxPoint, diffMax + sameCnt);
}
return maxPoint;
}
};
我贴个我的算法吧，你贴个你的标准答案，比一下就好了,咱们思路差太多。
【在 i******s 的大作中提到】
: 忍不住替habbit说一句，如果枚举所有点，并且每次内循环前用新的hashmap的话，可
: 以只存斜率，因为此时之前一点已经固定(外层循环确定起始点)，所以可以用斜率做
: key。但是如果hashmap不是每次内循环前创建，而是在双重循序前创建，那么截距是一
: 定要的，光slope不够。还有这道题用slope有精度问题，
: 消除方法最简单就是换个直线表示方式，用Ax+By+C = 0。其中A, B和C都是整数，每两
: 个点构成的直线都这样表示，注意用gcd法保证A,B和C没有公约数，并且保证符号相
: 同(可以假设A永远是正)。而且这道题最大的trick是如何处理重复的点，一般没做过的
: 第一次做不一定想得到好办法。总体看之前的讨论无语了，跳出来说几句。
template <>
struct hash
{
typedef std::size_t result_type;
result_type operator()(const pair
{ return ((long)t.first * 1000003 + t.second )& (((long)1<<32 ) - 1);
}
};
}
class Solution {
public:
// suppose no two points are the same
int gcd(int a, int b)
{ return !b? a: gcd(b, a %b); }
pair
{
int x1 = points[pointI].x, y1 = points[pointI].y,
x2 = points[pointJ].x, y2 = points[pointJ].y;
int diffy = y1 - y2, diffx = x1 - x2;
if(diffy == 0 || diffx == 0)
{
if(diffy == 0) diffx = 1;
if(diffx == 0) diffy = 1;
return make_pair(diffy, diffx);
}
if(diffy < 0)
{
diffy = -diffy;
diffx = -diffx;
}
int gcdVal = gcd(abs(diffy), abs(diffx));
return make_pair(diffy/gcdVal, diffx/gcdVal);
}
bool samePoint(vector
{ return points[pointI].x == points[pointJ].x && points[pointI].y ==
points[pointJ].y; }
/*
string intToStr(int val)
{
if(!val) return "0";
string str = "";
while(val)
{
str += val %10 + '0';
val /= 10;
}
reverse(str.begin(), str.end());
return str;
}
string pairToStr(pair
{ return intToStr(p.first) + " " + intToStr(p.second);}
＊/
int maxPoints(vector
unordered_map
int maxPoint = 0;
for(int pointI = 0; pointI < points.size(); ++ pointI)
{
map.clear();
int sameCnt = 1, diffMax = 0;
for(int pointJ = 0; pointJ < points.size(); ++ pointJ)
{
if(pointI == pointJ) continue;
if(samePoint(points, pointI, pointJ))
{
++ sameCnt;
continue;
}
pair
if(map.find(kval) == map.end())
map[kval] = 1;
else
++map[kval];
diffMax = max(diffMax, map[kval]);
}
maxPoint = max(maxPoint, diffMax + sameCnt);
}
return maxPoint;
}
};
我贴个我的算法吧，你贴个你的标准答案，比一下就好了,咱们思路差太多。
【在 i******s 的大作中提到】
: 忍不住替habbit说一句，如果枚举所有点，并且每次内循环前用新的hashmap的话，可
: 以只存斜率，因为此时之前一点已经固定(外层循环确定起始点)，所以可以用斜率做
: key。但是如果hashmap不是每次内循环前创建，而是在双重循序前创建，那么截距是一
: 定要的，光slope不够。还有这道题用slope有精度问题，
: 消除方法最简单就是换个直线表示方式，用Ax+By+C = 0。其中A, B和C都是整数，每两
: 个点构成的直线都这样表示，注意用gcd法保证A,B和C没有公约数，并且保证符号相
: 同(可以假设A永远是正)。而且这道题最大的trick是如何处理重复的点，一般没做过的
: 第一次做不一定想得到好办法。总体看之前的讨论无语了，跳出来说几句。
R*0
95 楼
是啊，我之前自己家的朋友家的再加上shelter volunteer见过的，也不少猫了，从来
没想过小猫咪能这么凶这么有杀伤力。。。以前总觉得my cat from hell离自己很遥远
。。。
【在 H******o 的大作中提到】
: 小美女好有性格啊，这么看起来lz我碰到的猫脾气都很好很好啊。。。。
: 有朋友家的猫放我家寄养。来了以后就四处视察，见到我的猫炸毛也无所谓。看到人就
: 翻肚皮求吃的。。。。
: 有我家二毛，来了以后隔离在厕所，听到我的声音，隔着厕所门都能听见她打呼噜的咕
: 咕声音。见到我亲的就像见到了娘。只要放出厕所，立刻上蹿下跳。把家里大猫搞得不
: 能安生。。。
没想过小猫咪能这么凶这么有杀伤力。。。以前总觉得my cat from hell离自己很遥远
。。。
【在 H******o 的大作中提到】
: 小美女好有性格啊，这么看起来lz我碰到的猫脾气都很好很好啊。。。。
: 有朋友家的猫放我家寄养。来了以后就四处视察，见到我的猫炸毛也无所谓。看到人就
: 翻肚皮求吃的。。。。
: 有我家二毛，来了以后隔离在厕所，听到我的声音，隔着厕所门都能听见她打呼噜的咕
: 咕声音。见到我亲的就像见到了娘。只要放出厕所，立刻上蹿下跳。把家里大猫搞得不
: 能安生。。。
i*s
96 楼
之前回的有误，请看我更正后的解答，你这样行是因为每次内循环前都clear了map。如
果换一个实现，则一定要存截距。anyway，slope的精度问题如果面试官死扣，那就只
能换Ax+By+C的表示方式，如果让过就过了。我碰到过both。
);
【在 h*******e 的大作中提到】
: namespace std {
: template <>
: struct hash >
: {
: typedef std::size_t result_type;
: result_type operator()(const pair & t) const
: { return ((long)t.first * 1000003 + t.second )& (((long)1<<32 ) - 1);
: }
: };
: }
果换一个实现，则一定要存截距。anyway，slope的精度问题如果面试官死扣，那就只
能换Ax+By+C的表示方式，如果让过就过了。我碰到过both。
);
【在 h*******e 的大作中提到】
: namespace std {
: template <>
: struct hash
: {
: typedef std::size_t result_type;
: result_type operator()(const pair
: { return ((long)t.first * 1000003 + t.second )& (((long)1<<32 ) - 1);
: }
: };
: }
R*0
97 楼
指甲前天晚上虐猫一般地剪掉了，强抱是绝对不敢的，欢迎来我家尝试。。。
【在 b*****e 的大作中提到】
: 指甲剪掉强抱是王道，俺最近就收拾了一只，三两天就主动爬上肚子了
【在 b*****e 的大作中提到】
: 指甲剪掉强抱是王道，俺最近就收拾了一只，三两天就主动爬上肚子了
h*e
98 楼
我的是check 了 Ａ＝０ Ｂ＝０的情况其实并不是严格意义上的斜率，垂直水平
是 ０， １ 和 １， ０ 一轴心点加上一方向自然能确定一条直线。
【在 i******s 的大作中提到】
: 之前回的有误，请看我更正后的解答，你这样行是因为每次内循环前都clear了map。如
: 果换一个实现，则一定要存截距。anyway，slope的精度问题如果面试官死扣，那就只
: 能换Ax+By+C的表示方式，如果让过就过了。我碰到过both。
:
: );
是 ０， １ 和 １， ０ 一轴心点加上一方向自然能确定一条直线。
【在 i******s 的大作中提到】
: 之前回的有误，请看我更正后的解答，你这样行是因为每次内循环前都clear了map。如
: 果换一个实现，则一定要存截距。anyway，slope的精度问题如果面试官死扣，那就只
: 能换Ax+By+C的表示方式，如果让过就过了。我碰到过both。
:
: );
R*0
99 楼
含泪握手。。。真的是这样的。。。
【在 N******t 的大作中提到】
: 真的会突然尖叫着冲上来攻击阿。。。吓死我的小心肝了
【在 N******t 的大作中提到】
: 真的会突然尖叫着冲上来攻击阿。。。吓死我的小心肝了
i*s
100 楼
你的解法没问题，只是要记得为什么可以不保存截距，只用"斜率"就可以。有的面试官
会confuse，因为可能他们没有想过如果每次内循环前清了map(或者创建一个新的)，则
截距不是必须的。因为一个点在外循环是已确定。如果碰上绕不过的新手面试官，建议
保存截距以迎合他们的口味。。。
【在 h*******e 的大作中提到】
: 我的是check 了 Ａ＝０ Ｂ＝０的情况其实并不是严格意义上的斜率，垂直水平
: 是 ０， １ 和 １， ０ 一轴心点加上一方向自然能确定一条直线。
会confuse，因为可能他们没有想过如果每次内循环前清了map(或者创建一个新的)，则
截距不是必须的。因为一个点在外循环是已确定。如果碰上绕不过的新手面试官，建议
保存截距以迎合他们的口味。。。
【在 h*******e 的大作中提到】
: 我的是check 了 Ａ＝０ Ｂ＝０的情况其实并不是严格意义上的斜率，垂直水平
: 是 ０， １ 和 １， ０ 一轴心点加上一方向自然能确定一条直线。
R*0
101 楼
谢谢！这就是我目前最大的安慰了~~
【在 B**********A 的大作中提到】
: 美女！
【在 B**********A 的大作中提到】
: 美女！
p*e
102 楼
A,B,C的解法更局限一点吧，因为只适用于整数情况
如果点是浮点的话，还是要考虑精度问题
【在 i******s 的大作中提到】
: 之前回的有误，请看我更正后的解答，你这样行是因为每次内循环前都clear了map。如
: 果换一个实现，则一定要存截距。anyway，slope的精度问题如果面试官死扣，那就只
: 能换Ax+By+C的表示方式，如果让过就过了。我碰到过both。
:
: );
如果点是浮点的话，还是要考虑精度问题
【在 i******s 的大作中提到】
: 之前回的有误，请看我更正后的解答，你这样行是因为每次内循环前都clear了map。如
: 果换一个实现，则一定要存截距。anyway，slope的精度问题如果面试官死扣，那就只
: 能换Ax+By+C的表示方式，如果让过就过了。我碰到过both。
:
: );
b*e
103 楼
给个地址吧，俺知道你也在猴子屯，让俺来教你怎么强抱猫
【在 R******0 的大作中提到】
: 指甲前天晚上虐猫一般地剪掉了，强抱是绝对不敢的，欢迎来我家尝试。。。
【在 R******0 的大作中提到】
: 指甲前天晚上虐猫一般地剪掉了，强抱是绝对不敢的，欢迎来我家尝试。。。
i*s
104 楼
well, 一般遇到的都是point是int x, int y。如果面试官扣这个，那就只有跟他聊聊
怎么解决精度问题了。但对于都是int的情况，ABC法比较好。
【在 p****e 的大作中提到】
: A,B,C的解法更局限一点吧，因为只适用于整数情况
: 如果点是浮点的话，还是要考虑精度问题
怎么解决精度问题了。但对于都是int的情况，ABC法比较好。
【在 p****e 的大作中提到】
: A,B,C的解法更局限一点吧，因为只适用于整数情况
: 如果点是浮点的话，还是要考虑精度问题
R*0
105 楼
是啊，有时候看奶昔那么漂亮趴在那就想，怎么能这么凶呢？太迷惑人了
【在 L*********3 的大作中提到】
: 哈哈哈，美女果然有脾气！
【在 L*********3 的大作中提到】
: 哈哈哈，美女果然有脾气！
h*e
106 楼
浮点要考虑精度问题的而且这时候要重写 unordered_map的equal函数了， 我现在还
没想清楚为什么这个 哈希函数一定要外面加个namespace std才能通过。
这种template我之前也没见过 搜了一下发现叫做全特化模板。
【在 p****e 的大作中提到】
: A,B,C的解法更局限一点吧，因为只适用于整数情况
: 如果点是浮点的话，还是要考虑精度问题
没想清楚为什么这个 哈希函数一定要外面加个namespace std才能通过。
这种template我之前也没见过 搜了一下发现叫做全特化模板。
【在 p****e 的大作中提到】
: A,B,C的解法更局限一点吧，因为只适用于整数情况
: 如果点是浮点的话，还是要考虑精度问题
N*t
107 楼
其实猫还是很可怜阿，他们攻击也是因为太害怕了，觉得实在被逼的走投无路了。问题
是跟他示好他也不领情。。。我觉得可能还是冷处理，晾着他比较好
【在 R******0 的大作中提到】
: 含泪握手。。。真的是这样的。。。
是跟他示好他也不领情。。。我觉得可能还是冷处理，晾着他比较好
【在 R******0 的大作中提到】
: 含泪握手。。。真的是这样的。。。
h*e
108 楼
轴心点 pointI 给定了 知道了 Ａ Ｂ就能知道 C了所以两个值就够了
【在 i******s 的大作中提到】
: 之前回的有误，请看我更正后的解答，你这样行是因为每次内循环前都clear了map。如
: 果换一个实现，则一定要存截距。anyway，slope的精度问题如果面试官死扣，那就只
: 能换Ax+By+C的表示方式，如果让过就过了。我碰到过both。
:
: );
【在 i******s 的大作中提到】
: 之前回的有误，请看我更正后的解答，你这样行是因为每次内循环前都clear了map。如
: 果换一个实现，则一定要存截距。anyway，slope的精度问题如果面试官死扣，那就只
: 能换Ax+By+C的表示方式，如果让过就过了。我碰到过both。
:
: );
R*0
109 楼
就是这样啊，其实很想让她知道我们一点都不可怕。。。所以我想要不要早点让可乐雪
碧跟奶昔见面，告诉她我们都是好人~~要等奶昔对我们完全放下戒备再让他们仨见面的
话，不知道还要多久啊
【在 N******t 的大作中提到】
: 其实猫还是很可怜阿，他们攻击也是因为太害怕了，觉得实在被逼的走投无路了。问题
: 是跟他示好他也不领情。。。我觉得可能还是冷处理，晾着他比较好
碧跟奶昔见面，告诉她我们都是好人~~要等奶昔对我们完全放下戒备再让他们仨见面的
话，不知道还要多久啊
【在 N******t 的大作中提到】
: 其实猫还是很可怜阿，他们攻击也是因为太害怕了，觉得实在被逼的走投无路了。问题
: 是跟他示好他也不领情。。。我觉得可能还是冷处理，晾着他比较好
h*e
110 楼
rt
给定平面上n点，求在同一直线上最多点问题～～大家用double /float 类型作hash
key么？
判断两个double /float 类型相等～～～ 靠谱么
给定平面上n点，求在同一直线上最多点问题～～大家用double /float 类型作hash
key么？
判断两个double /float 类型相等～～～ 靠谱么
g*y
111 楼
我养老二的时候被攻击过多次，整个手臂伤痕累累。 直到半年多，还会时不时hiss一
下。 2年后开始亲人，现在10年了，温柔的不行。。。。 漫长的过程。
【在 R******0 的大作中提到】
: 含泪握手。。。真的是这样的。。。
下。 2年后开始亲人，现在10年了，温柔的不行。。。。 漫长的过程。
【在 R******0 的大作中提到】
: 含泪握手。。。真的是这样的。。。
y*n
112 楼
不是可以设一个比较小的数， 0.0000001， 然后和这个数比较就可以吗？
R*0
113 楼
啊，我真是倍受鼓舞啊！看来我之前开玩笑说的一年期限还真有必要。。。
【在 g*****y 的大作中提到】
: 我养老二的时候被攻击过多次，整个手臂伤痕累累。 直到半年多，还会时不时hiss一
: 下。 2年后开始亲人，现在10年了，温柔的不行。。。。 漫长的过程。
【在 g*****y 的大作中提到】
: 我养老二的时候被攻击过多次，整个手臂伤痕累累。 直到半年多，还会时不时hiss一
: 下。 2年后开始亲人，现在10年了，温柔的不行。。。。 漫长的过程。
h*e
114 楼
找到一个链接，关于float做key
“HOWEVER, you should not be using a floating point for any part of a key in
any map -- for the same reason you shouldn't use them with == and !=
operators. Since floating points are approximations, they are unreliable as
keys.“
http://www.cplusplus.com/forum/beginner/56918/
【在 y***n 的大作中提到】
: 不是可以设一个比较小的数， 0.0000001， 然后和这个数比较就可以吗？
“HOWEVER, you should not be using a floating point for any part of a key in
any map -- for the same reason you shouldn't use them with == and !=
operators. Since floating points are approximations, they are unreliable as
keys.“
http://www.cplusplus.com/forum/beginner/56918/
【在 y***n 的大作中提到】
: 不是可以设一个比较小的数， 0.0000001， 然后和这个数比较就可以吗？
x*a
115 楼
美得无法自拔...
【在 R******0 的大作中提到】
: 自上周一与猫爸猫妈亲密接触以后，奶昔饮食正常，情绪稳(fanfu)定(wuchang)，曾经
: 被当成砂盆的南瓜窝也变成了好地方~~
: 每天晚饭时间，可乐和雪碧被邀请到包厢享受大餐，奶昔闻着俩陌生喵的味道淡去，小
: 心地踱到门外，四处张望
: 坐得好累，趴一会，翻过来，又翻过去，似乎真的没有什么危险了
: 这个黑黑的大盒子是什么东西，上去看看
: 啊，这里看起来很隐蔽，是个休息的好地方
: 没人看我吧，我去那边开阔地带转转
: 不好！有人来了！赶紧找机会回去！
: 就这样，奶昔每天在外面晃悠的时间越来越长，直到有一天，在被猫妈试图抚摸未果的
【在 R******0 的大作中提到】
: 自上周一与猫爸猫妈亲密接触以后，奶昔饮食正常，情绪稳(fanfu)定(wuchang)，曾经
: 被当成砂盆的南瓜窝也变成了好地方~~
: 每天晚饭时间，可乐和雪碧被邀请到包厢享受大餐，奶昔闻着俩陌生喵的味道淡去，小
: 心地踱到门外，四处张望
: 坐得好累，趴一会，翻过来，又翻过去，似乎真的没有什么危险了
: 这个黑黑的大盒子是什么东西，上去看看
: 啊，这里看起来很隐蔽，是个休息的好地方
: 没人看我吧，我去那边开阔地带转转
: 不好！有人来了！赶紧找机会回去！
: 就这样，奶昔每天在外面晃悠的时间越来越长，直到有一天，在被猫妈试图抚摸未果的
s*x
116 楼
Cc150 介绍的非常清楚了吧？
P*D
117 楼
最近去你家那只？这么刺激啊，早知道就竞争一下了
★ 发自iPhone App: ChineseWeb 7.8
【在 N******t 的大作中提到】
: 真的会突然尖叫着冲上来攻击阿。。。吓死我的小心肝了
★ 发自iPhone App: ChineseWeb 7.8
【在 N******t 的大作中提到】
: 真的会突然尖叫着冲上来攻击阿。。。吓死我的小心肝了
h*e
118 楼
记不清了，能告诉一下第几章地几题么。
【在 s**x 的大作中提到】
: Cc150 介绍的非常清楚了吧？
【在 s**x 的大作中提到】
: Cc150 介绍的非常清楚了吧？
R*0
119 楼
太荣幸了~~
【在 x*********a 的大作中提到】
: 美得无法自拔...
【在 x*********a 的大作中提到】
: 美得无法自拔...
j*8
120 楼
正准备发个类似的问题，就在这里说了
有人面这题时因为用 double / float 作为 hashmap的key而被面试官说的吗？？
有人面这题时因为用 double / float 作为 hashmap的key而被面试官说的吗？？
l*y
121 楼
惜惜太美貌了，抱来亲亲。 赞妹妹和家人！都好有爱心和耐心！
s*x
122 楼
自己查查
【在 h*******e 的大作中提到】
: 记不清了，能告诉一下第几章地几题么。
【在 h*******e 的大作中提到】
: 记不清了，能告诉一下第几章地几题么。
w*i
123 楼
太美了 摸摸
h*e
124 楼
翻了一遍没找到，好久不看了。
你用第四版吧 我是第五版，
第四版10.6 找到了， java 可以自定义类型作为key的，c++ 就不行。
【在 s**x 的大作中提到】
: 自己查查
你用第四版吧 我是第五版，
第四版10.6 找到了， java 可以自定义类型作为key的，c++ 就不行。
【在 s**x 的大作中提到】
: 自己查查
R*0
125 楼
争取能早点抱着亲亲啊~~好久没见Abby了，现在怎么样啊
【在 l*********y 的大作中提到】
: 惜惜太美貌了，抱来亲亲。 赞妹妹和家人！都好有爱心和耐心！
【在 l*********y 的大作中提到】
: 惜惜太美貌了，抱来亲亲。 赞妹妹和家人！都好有爱心和耐心！
p*e
126 楼
可以取整，我就是这样做的
int slope = (int)(1000000.*float(p2.y-p1.y)/(p2.x-p1.x));
int slope = (int)(1000000.*float(p2.y-p1.y)/(p2.x-p1.x));
R*0
127 楼
目前在脑门啊下巴啊脖子附近摸摸都还比较安全。。。
【在 w******i 的大作中提到】
: 太美了 摸摸
【在 w******i 的大作中提到】
: 太美了 摸摸
s*x
128 楼
第五版7.6
【在 h*******e 的大作中提到】
: 翻了一遍没找到，好久不看了。
: 你用第四版吧 我是第五版，
: 第四版10.6 找到了， java 可以自定义类型作为key的，c++ 就不行。
w*i
129 楼
笑死了 我家的也随时发作阿 有时候一边purr一边冲上来攻击
【在 R******0 的大作中提到】
: 目前在脑门啊下巴啊脖子附近摸摸都还比较安全。。。
【在 R******0 的大作中提到】
: 目前在脑门啊下巴啊脖子附近摸摸都还比较安全。。。
h*e
130 楼
谢谢看到cc150给的方法了。觉得给的解法还是比较一般。。。计算几何里面很少用k
来决定点在一条直线上。k在靠近原点一小变很可能导致点在 距离原点远处一大变。
【在 s**x 的大作中提到】
:
: 第五版7.6
来决定点在一条直线上。k在靠近原点一小变很可能导致点在 距离原点远处一大变。
【在 s**x 的大作中提到】
:
: 第五版7.6
l*y
131 楼
Abby依旧是个乖孩子，见到谁到我家了，也不管人不认识就往人家身上蹭和闻，绝对是
个狗狗猫，呵呵。 他现在都快12磅了。
【在 R******0 的大作中提到】
: 争取能早点抱着亲亲啊~~好久没见Abby了，现在怎么样啊
个狗狗猫，呵呵。 他现在都快12磅了。
【在 R******0 的大作中提到】
: 争取能早点抱着亲亲啊~~好久没见Abby了，现在怎么样啊
g*e
132 楼
如果坐标是整数的话，斜率都是有理数。可以存pair
【在 h*******e 的大作中提到】
: rt
: 给定平面上n点，求在同一直线上最多点问题～～大家用double /float 类型作hash
: key么？
: 判断两个double /float 类型相等～～～ 靠谱么
【在 h*******e 的大作中提到】
: rt
: 给定平面上n点，求在同一直线上最多点问题～～大家用double /float 类型作hash
: key么？
: 判断两个double /float 类型相等～～～ 靠谱么
R*0
133 楼
看来美猫真是会脾气大一些啊，一点点不爽都要表现出来~~~
【在 w******i 的大作中提到】
: 笑死了 我家的也随时发作阿 有时候一边purr一边冲上来攻击
【在 w******i 的大作中提到】
: 笑死了 我家的也随时发作阿 有时候一边purr一边冲上来攻击
h*e
134 楼
如果是pair作为 key 的话自定义的hash 函数一般怎么写
在 c++ unordered_set, int> 大牛给讲一下哦。
【在 g*********e 的大作中提到】
: 如果坐标是整数的话，斜率都是有理数。可以存pair
在 c++ unordered_set
【在 g*********e 的大作中提到】
: 如果坐标是整数的话，斜率都是有理数。可以存pair
R*0
135 楼
一直在茁壮成长啊！雪碧彻底停在11磅了，8个月没变过了。。。可乐雪碧见客人也是
可大方了，希望能给奶昔带个好榜样~~
【在 l*********y 的大作中提到】
: Abby依旧是个乖孩子，见到谁到我家了，也不管人不认识就往人家身上蹭和闻，绝对是
: 个狗狗猫，呵呵。 他现在都快12磅了。
可大方了，希望能给奶昔带个好榜样~~
【在 l*********y 的大作中提到】
: Abby依旧是个乖孩子，见到谁到我家了，也不管人不认识就往人家身上蹭和闻，绝对是
: 个狗狗猫，呵呵。 他现在都快12磅了。
g*e
136 楼
你写的对
【在 h*******e 的大作中提到】
: 如果是pair作为 key 的话自定义的hash 函数一般怎么写
: 在 c++ unordered_set, int> 大牛给讲一下哦。
【在 h*******e 的大作中提到】
: 如果是pair作为 key 的话自定义的hash 函数一般怎么写
: 在 c++ unordered_set
l*y
137 楼
说实话abby真不是吃过，我上周试着把肉塞到他嘴里，让他尝一下，想着说不定就喜欢
吃了，结果这货直接给我吐出来了。雪碧对奶昔没问题，估计可乐会有点小心眼，呵呵
【在 R******0 的大作中提到】
: 一直在茁壮成长啊！雪碧彻底停在11磅了，8个月没变过了。。。可乐雪碧见客人也是
: 可大方了，希望能给奶昔带个好榜样~~
吃了，结果这货直接给我吐出来了。雪碧对奶昔没问题，估计可乐会有点小心眼，呵呵
【在 R******0 的大作中提到】
: 一直在茁壮成长啊！雪碧彻底停在11磅了，8个月没变过了。。。可乐雪碧见客人也是
: 可大方了，希望能给奶昔带个好榜样~~
h*e
138 楼
光是这个过不了leetcode的编译器阿，需要自定义hash 函数，和比较函数的似乎。
【在 g*********e 的大作中提到】
: 你写的对
【在 g*********e 的大作中提到】
: 你写的对
s*a
139 楼
太美了
【在 R******0 的大作中提到】
: 自上周一与猫爸猫妈亲密接触以后，奶昔饮食正常，情绪稳(fanfu)定(wuchang)，曾经
: 被当成砂盆的南瓜窝也变成了好地方~~
: 每天晚饭时间，可乐和雪碧被邀请到包厢享受大餐，奶昔闻着俩陌生喵的味道淡去，小
: 心地踱到门外，四处张望
: 坐得好累，趴一会，翻过来，又翻过去，似乎真的没有什么危险了
: 这个黑黑的大盒子是什么东西，上去看看
: 啊，这里看起来很隐蔽，是个休息的好地方
: 没人看我吧，我去那边开阔地带转转
: 不好！有人来了！赶紧找机会回去！
: 就这样，奶昔每天在外面晃悠的时间越来越长，直到有一天，在被猫妈试图抚摸未果的
【在 R******0 的大作中提到】
: 自上周一与猫爸猫妈亲密接触以后，奶昔饮食正常，情绪稳(fanfu)定(wuchang)，曾经
: 被当成砂盆的南瓜窝也变成了好地方~~
: 每天晚饭时间，可乐和雪碧被邀请到包厢享受大餐，奶昔闻着俩陌生喵的味道淡去，小
: 心地踱到门外，四处张望
: 坐得好累，趴一会，翻过来，又翻过去，似乎真的没有什么危险了
: 这个黑黑的大盒子是什么东西，上去看看
: 啊，这里看起来很隐蔽，是个休息的好地方
: 没人看我吧，我去那边开阔地带转转
: 不好！有人来了！赶紧找机会回去！
: 就这样，奶昔每天在外面晃悠的时间越来越长，直到有一天，在被猫妈试图抚摸未果的
P*L
140 楼
这样做是最好的，但是还得找最大公约数，容易超时过不了 oj。
【在 g*********e 的大作中提到】
: 如果坐标是整数的话，斜率都是有理数。可以存pair
【在 g*********e 的大作中提到】
: 如果坐标是整数的话，斜率都是有理数。可以存pair
f*a
141 楼
小奶昔太美了!!! 好俏丽啊
h*e
142 楼
要自己加hash function的，我写了一个总算过了编译了
namespace std {
template <>
struct hash >
{
typedef std::size_t result_type;
result_type operator()(const pair & t) const
{
return t.first * 1000003 + t.second;
}
};
}
备注 (不过似乎不太好~~ 似乎 hash值 溢出了~~~ )但是也过了oj了。
有没有人写过这个hash, 这个似乎是c++ 0x/11新标准 ~~这个hash函数该怎么写才能
写得简单少冲突而又 不越界呢~~
gcd非常少的代码的。就是辗转相除一行代码就行。
【在 P*******L 的大作中提到】
: 这样做是最好的，但是还得找最大公约数，容易超时过不了 oj。
namespace std {
template <>
struct hash
{
typedef std::size_t result_type;
result_type operator()(const pair
{
return t.first * 1000003 + t.second;
}
};
}
备注 (不过似乎不太好~~ 似乎 hash值 溢出了~~~ )但是也过了oj了。
有没有人写过这个hash, 这个似乎是c++ 0x/11新标准 ~~这个hash函数该怎么写才能
写得简单少冲突而又 不越界呢~~
gcd非常少的代码的。就是辗转相除一行代码就行。
【在 P*******L 的大作中提到】
: 这样做是最好的，但是还得找最大公约数，容易超时过不了 oj。
g*e
143 楼
set, int>
这个直接就可以用啊
想过leetcode的话用floating的比较就足够了，但google面试的时候我用floating的斜
率 Interviewer就不让过
这个直接就可以用啊
想过leetcode的话用floating的比较就足够了，但google面试的时候我用floating的斜
率 Interviewer就不让过
h*e
144 楼
google 是要求pair 做斜率么？
google是要求精确在一条直线上， 还是要求近似的可以有些误差的点也算一条线阿。
请大牛给细说说g关于这道题的要求阿。
【在 g*********e 的大作中提到】
: set, int>
: 这个直接就可以用啊
: 想过leetcode的话用floating的比较就足够了，但google面试的时候我用floating的斜
: 率 Interviewer就不让过
google是要求精确在一条直线上， 还是要求近似的可以有些误差的点也算一条线阿。
请大牛给细说说g关于这道题的要求阿。
【在 g*********e 的大作中提到】
: set
: 这个直接就可以用啊
: 想过leetcode的话用floating的比较就足够了，但google面试的时候我用floating的斜
: 率 Interviewer就不让过
g*e
145 楼
要精确的 不能用epsilon这样去比。不过也看面试官吧
【在 h*******e 的大作中提到】
: google 是要求pair
: google是要求精确在一条直线上， 还是要求近似的可以有些误差的点也算一条线阿。
: 请大牛给细说说g关于这道题的要求阿。
h*e
146 楼
恩恩，多谢了。
【在 g*********e 的大作中提到】
:
: 要精确的 不能用epsilon这样去比。不过也看面试官吧
【在 g*********e 的大作中提到】
:
: 要精确的 不能用epsilon这样去比。不过也看面试官吧
f*5
147 楼
有一个思路不知道对不对，用unordered_map
斜率可以表示成循环小数, 比如5/6=0.8(3)， 还没在leetcode上试，不知道能不能过
【在 h*******e 的大作中提到】
: 要自己加hash function的，我写了一个总算过了编译了
: namespace std {
: template <>
: struct hash
: {
: typedef std::size_t result_type;
: result_type operator()(const pair
: {
: return t.first * 1000003 + t.second;
: }
s*5
148 楼
use hash of hash: unordered_map >
【在 h*******e 的大作中提到】
: 如果是pair作为 key 的话自定义的hash 函数一般怎么写
: 在 c++ unordered_set, int> 大牛给讲一下哦。
【在 h*******e 的大作中提到】
: 如果是pair作为 key 的话自定义的hash 函数一般怎么写
: 在 c++ unordered_set
h*e
149 楼
我之前用的map 把 pair 的两个 int 变成string 中间加上
" "然后再加上 string 变成一个长string 你的方法也是对的一个 无理数唯一对应
一个非循环，和循环部分的组合。就是这个求循环节的过程比较麻烦了，估计你数学功
底很好，可以很快求出来。
【在 f*******5 的大作中提到】
:
: 有一个思路不知道对不对，用unordered_map, 因为点坐标是整数，所以
: 斜率可以表示成循环小数, 比如5/6=0.8(3)， 还没在leetcode上试，不知道能不能过
" "然后再加上 string 变成一个长string 你的方法也是对的一个 无理数唯一对应
一个非循环，和循环部分的组合。就是这个求循环节的过程比较麻烦了，估计你数学功
底很好，可以很快求出来。
【在 f*******5 的大作中提到】
:
: 有一个思路不知道对不对，用unordered_map
: 斜率可以表示成循环小数, 比如5/6=0.8(3)， 还没在leetcode上试，不知道能不能过
h*e
150 楼
是不是key value类型写反了，而且复杂的类型做key比较麻烦在leetcode 定义就不可
以，vs2010定义没问题，但是往里面map[key]= val 赋值时候就编译不过了。
【在 s***5 的大作中提到】
: use hash of hash: unordered_map >
以，vs2010定义没问题，但是往里面map[key]= val 赋值时候就编译不过了。
【在 s***5 的大作中提到】
: use hash of hash: unordered_map
f*5
151 楼
有个Google面试题是求整数除法的循环，是不断用余数做被除数，用一个bool arr[10]
记录被除数，当前被除数如果见过就表示循环
【在 h*******e 的大作中提到】
: 是不是key value类型写反了，而且复杂的类型做key比较麻烦在leetcode 定义就不可
: 以，vs2010定义没问题，但是往里面map[key]= val 赋值时候就编译不过了。
h*e
152 楼
呵呵，估计写得好能小impress面试官一下，本想出一道难题，没成想面试者一口气完
成了两道难题。
10]
【在 f*******5 的大作中提到】
:
: 有个Google面试题是求整数除法的循环，是不断用余数做被除数，用一个bool arr[10]
: 记录被除数，当前被除数如果见过就表示循环
成了两道难题。
10]
【在 f*******5 的大作中提到】
:
: 有个Google面试题是求整数除法的循环，是不断用余数做被除数，用一个bool arr[10]
: 记录被除数，当前被除数如果见过就表示循环
y*n
153 楼
那Sqrt 那个题可以用epsilon吗？
【在 g*********e 的大作中提到】
:
: 要精确的 不能用epsilon这样去比。不过也看面试官吧
【在 g*********e 的大作中提到】
:
: 要精确的 不能用epsilon这样去比。不过也看面试官吧
g*e
154 楼
记得数学的算cross product
不记得的斜率公式转换一下变乘法，其实就是叉乘
【在 g*********e 的大作中提到】
: set, int>
: 这个直接就可以用啊
: 想过leetcode的话用floating的比较就足够了，但google面试的时候我用floating的斜
: 率 Interviewer就不让过
不记得的斜率公式转换一下变乘法，其实就是叉乘
【在 g*********e 的大作中提到】
: set
: 这个直接就可以用啊
: 想过leetcode的话用floating的比较就足够了，但google面试的时候我用floating的斜
: 率 Interviewer就不让过
g*e
155 楼
表示成2/7=0.[285714]
10]
【在 f*******5 的大作中提到】
:
: 有个Google面试题是求整数除法的循环，是不断用余数做被除数，用一个bool arr[10]
: 记录被除数，当前被除数如果见过就表示循环
10]
【在 f*******5 的大作中提到】
:
: 有个Google面试题是求整数除法的循环，是不断用余数做被除数，用一个bool arr[10]
: 记录被除数，当前被除数如果见过就表示循环
g*e
156 楼
可以
【在 y***n 的大作中提到】
: 那Sqrt 那个题可以用epsilon吗？
【在 y***n 的大作中提到】
: 那Sqrt 那个题可以用epsilon吗？
y*n
157 楼
你搞得那么细，以后可以写一本书。每个题写：
A. 基本解法。
A-1. Google解法。
A-2。Facebook 解法。
A-3。 Linkedin解法。
【在 h*******e 的大作中提到】
: google 是要求pair 做斜率么？
: google是要求精确在一条直线上， 还是要求近似的可以有些误差的点也算一条线阿。
: 请大牛给细说说g关于这道题的要求阿。
A. 基本解法。
A-1. Google解法。
A-2。Facebook 解法。
A-3。 Linkedin解法。
【在 h*******e 的大作中提到】
: google 是要求pair
: google是要求精确在一条直线上， 还是要求近似的可以有些误差的点也算一条线阿。
: 请大牛给细说说g关于这道题的要求阿。
h*e
158 楼
你多做些计算几何题就知道了，计算几何差一点就差很多， 比如三点共线的标准方法
就是叉乘面积近似为0，近似斜率做就引进边的长度误差，计算几何在严格一点的oj上都
是差之毫厘，失之千里的，过了leetcode的 oj的做法很多不一定就一定无懈可击，往
往面试难得不是原题，而是是要求改一点，比如这道题之前c++ 不支持 unordered_set
的时候就看过这道题，那要高效算法就只能手动写链表hash table实现hash~~ 这道题
glowinglake 的 follow up 也不是那么简单说海量数据情况下应该怎么变我还没细想
。
by the way 关于sqrt 那道题 虽然可以用 epsilon但是有不用 epsilon的精确解法，
不知道你能不能想出来。
【在 y***n 的大作中提到】
: 你搞得那么细，以后可以写一本书。每个题写：
: A. 基本解法。
: A-1. Google解法。
: A-2。Facebook 解法。
: A-3。 Linkedin解法。
就是叉乘面积近似为0，近似斜率做就引进边的长度误差，计算几何在严格一点的oj上都
是差之毫厘，失之千里的，过了leetcode的 oj的做法很多不一定就一定无懈可击，往
往面试难得不是原题，而是是要求改一点，比如这道题之前c++ 不支持 unordered_set
的时候就看过这道题，那要高效算法就只能手动写链表hash table实现hash~~ 这道题
glowinglake 的 follow up 也不是那么简单说海量数据情况下应该怎么变我还没细想
。
by the way 关于sqrt 那道题 虽然可以用 epsilon但是有不用 epsilon的精确解法，
不知道你能不能想出来。
【在 y***n 的大作中提到】
: 你搞得那么细，以后可以写一本书。每个题写：
: A. 基本解法。
: A-1. Google解法。
: A-2。Facebook 解法。
: A-3。 Linkedin解法。
h*t
159 楼
这个能再多解释一下吗？
【在 g**e 的大作中提到】
: 记得数学的算cross product
: 不记得的斜率公式转换一下变乘法，其实就是叉乘
h*t
160 楼
弱问一句：为什么只存 slope作为key呢， 不需要存和 y轴交点吗？
【在 h*******e 的大作中提到】
: 如果是pair作为 key 的话自定义的hash 函数一般怎么写
: 在 c++ unordered_set
h*e
161 楼
不同的2点确定一条直线，确定一个直线方程，确定一斜率。
【在 h****t 的大作中提到】
:
: 弱问一句：为什么只存 slope作为key呢， 不需要存和 y轴交点吗？
【在 h****t 的大作中提到】
:
: 弱问一句：为什么只存 slope作为key呢， 不需要存和 y轴交点吗？
h*t
162 楼
我的意思是 会存在2条不同的平行直线（相同斜率）。
只存斜率无法区分这2条不同直线。
【在 h*******e 的大作中提到】
: 不同的2点确定一条直线，确定一个直线方程，确定一斜率。
只存斜率无法区分这2条不同直线。
【在 h*******e 的大作中提到】
: 不同的2点确定一条直线，确定一个直线方程，确定一斜率。
h*e
163 楼
我感觉你对这道题的总体思路还没有概念，为了不spoil你刷题的乐趣，你可以尝试思
考并且做一下leetcode第三题。max points on a line.
【在 h****t 的大作中提到】
: 我的意思是 会存在2条不同的平行直线（相同斜率）。
: 只存斜率无法区分这2条不同直线。
考并且做一下leetcode第三题。max points on a line.
【在 h****t 的大作中提到】
: 我的意思是 会存在2条不同的平行直线（相同斜率）。
: 只存斜率无法区分这2条不同直线。
h*t
164 楼
不知道你的感觉从何而来。
2年前面世时就被问过这题并且答案通过。leetcode什么的其它不多说了，没刷过的人
现在不多了。
"总体思路还没有概念"，嘿嘿，嘿嘿。我一笑而过。
【在 h*******e 的大作中提到】
: 我感觉你对这道题的总体思路还没有概念，为了不spoil你刷题的乐趣，你可以尝试思
: 考并且做一下leetcode第三题。max points on a line.
2年前面世时就被问过这题并且答案通过。leetcode什么的其它不多说了，没刷过的人
现在不多了。
"总体思路还没有概念"，嘿嘿，嘿嘿。我一笑而过。
【在 h*******e 的大作中提到】
: 我感觉你对这道题的总体思路还没有概念，为了不spoil你刷题的乐趣，你可以尝试思
: 考并且做一下leetcode第三题。max points on a line.
y*n
165 楼
他应该不是用 slope作为key呢
【在 h****t 的大作中提到】
: 不知道你的感觉从何而来。
: 2年前面世时就被问过这题并且答案通过。leetcode什么的其它不多说了，没刷过的人
: 现在不多了。
: "总体思路还没有概念"，嘿嘿，嘿嘿。我一笑而过。
【在 h****t 的大作中提到】
: 不知道你的感觉从何而来。
: 2年前面世时就被问过这题并且答案通过。leetcode什么的其它不多说了，没刷过的人
: 现在不多了。
: "总体思路还没有概念"，嘿嘿，嘿嘿。我一笑而过。
h*e
166 楼
哦那就是你刷题和我们大多数人的思路很不同哦，不妨你也介绍一下你的做法，大家开
阔思路哦。
我们是算每点和其他点的斜率，用斜率为key做hashmap, 看和本点相连的其他点落在
每个斜率内的有几个。 然后枚举这个轴心点 这样算法复杂度O(N*N)
我们现在都是用斜率作key 整个帖子纠结的是斜率怎么存和相应的精确度的问题，看
你说似乎不是用斜率做key,
所以开始还以为你没做过呢。
【在 h****t 的大作中提到】
: 不知道你的感觉从何而来。
: 2年前面世时就被问过这题并且答案通过。leetcode什么的其它不多说了，没刷过的人
: 现在不多了。
: "总体思路还没有概念"，嘿嘿，嘿嘿。我一笑而过。
阔思路哦。
我们是算每点和其他点的斜率，用斜率为key做hashmap, 看和本点相连的其他点落在
每个斜率内的有几个。 然后枚举这个轴心点 这样算法复杂度O(N*N)
我们现在都是用斜率作key 整个帖子纠结的是斜率怎么存和相应的精确度的问题，看
你说似乎不是用斜率做key,
所以开始还以为你没做过呢。
【在 h****t 的大作中提到】
: 不知道你的感觉从何而来。
: 2年前面世时就被问过这题并且答案通过。leetcode什么的其它不多说了，没刷过的人
: 现在不多了。
: "总体思路还没有概念"，嘿嘿，嘿嘿。我一笑而过。
i*s
167 楼
忍不住替habbit说一句，如果枚举所有点，并且每次内循环前用新的hashmap的话，可
以只存斜率，因为此时之前一点已经固定(外层循环确定起始点)，所以可以用斜率做
key。但是如果hashmap不是每次内循环前创建，而是在双重循序前创建，那么截距是一
定要的，光slope不够。还有这道题用slope有精度问题，
消除方法最简单就是换个直线表示方式，用Ax+By+C = 0。其中A, B和C都是整数，每两
个点构成的直线都这样表示，注意用gcd法保证A,B和C没有公约数，并且保证符号相
同(可以假设A永远是正)。而且这道题最大的trick是如何处理重复的点，一般没做过的
第一次做不一定想得到好办法。总体看之前的讨论无语了，跳出来说几句。
【在 h*******e 的大作中提到】
: 哦那就是你刷题和我们大多数人的思路很不同哦，不妨你也介绍一下你的做法，大家开
: 阔思路哦。
: 我们是算每点和其他点的斜率，用斜率为key做hashmap, 看和本点相连的其他点落在
: 每个斜率内的有几个。 然后枚举这个轴心点 这样算法复杂度O(N*N)
: 我们现在都是用斜率作key 整个帖子纠结的是斜率怎么存和相应的精确度的问题，看
: 你说似乎不是用斜率做key,
: 所以开始还以为你没做过呢。
以只存斜率，因为此时之前一点已经固定(外层循环确定起始点)，所以可以用斜率做
key。但是如果hashmap不是每次内循环前创建，而是在双重循序前创建，那么截距是一
定要的，光slope不够。还有这道题用slope有精度问题，
消除方法最简单就是换个直线表示方式，用Ax+By+C = 0。其中A, B和C都是整数，每两
个点构成的直线都这样表示，注意用gcd法保证A,B和C没有公约数，并且保证符号相
同(可以假设A永远是正)。而且这道题最大的trick是如何处理重复的点，一般没做过的
第一次做不一定想得到好办法。总体看之前的讨论无语了，跳出来说几句。
【在 h*******e 的大作中提到】
: 哦那就是你刷题和我们大多数人的思路很不同哦，不妨你也介绍一下你的做法，大家开
: 阔思路哦。
: 我们是算每点和其他点的斜率，用斜率为key做hashmap, 看和本点相连的其他点落在
: 每个斜率内的有几个。 然后枚举这个轴心点 这样算法复杂度O(N*N)
: 我们现在都是用斜率作key 整个帖子纠结的是斜率怎么存和相应的精确度的问题，看
: 你说似乎不是用斜率做key,
: 所以开始还以为你没做过呢。
h*e
168 楼
namespace std {
template <>
struct hash >
{
typedef std::size_t result_type;
result_type operator()(const pair & t) const
{ return ((long)t.first * 1000003 + t.second )& (((long)1<<32 ) - 1);
}
};
}
class Solution {
public:
// suppose no two points are the same
int gcd(int a, int b)
{ return !b? a: gcd(b, a %b); }
pair getK(vector & points, int pointI, int pointJ)
{
int x1 = points[pointI].x, y1 = points[pointI].y,
x2 = points[pointJ].x, y2 = points[pointJ].y;
int diffy = y1 - y2, diffx = x1 - x2;
if(diffy == 0 || diffx == 0)
{
if(diffy == 0) diffx = 1;
if(diffx == 0) diffy = 1;
return make_pair(diffy, diffx);
}
if(diffy < 0)
{
diffy = -diffy;
diffx = -diffx;
}
int gcdVal = gcd(abs(diffy), abs(diffx));
return make_pair(diffy/gcdVal, diffx/gcdVal);
}
bool samePoint(vector & points, int pointI, int pointJ)
{ return points[pointI].x == points[pointJ].x && points[pointI].y ==
points[pointJ].y; }
/*
string intToStr(int val)
{
if(!val) return "0";
string str = "";
while(val)
{
str += val %10 + '0';
val /= 10;
}
reverse(str.begin(), str.end());
return str;
}
string pairToStr(pair & p)
{ return intToStr(p.first) + " " + intToStr(p.second);}
＊/
int maxPoints(vector &points) {
unordered_map, int > map;
int maxPoint = 0;
for(int pointI = 0; pointI < points.size(); ++ pointI)
{
map.clear();
int sameCnt = 1, diffMax = 0;
for(int pointJ = 0; pointJ < points.size(); ++ pointJ)
{
if(pointI == pointJ) continue;
if(samePoint(points, pointI, pointJ))
{
++ sameCnt;
continue;
}
pair kval = getK(points, pointI, pointJ);
if(map.find(kval) == map.end())
map[kval] = 1;
else
++map[kval];
diffMax = max(diffMax, map[kval]);
}
maxPoint = max(maxPoint, diffMax + sameCnt);
}
return maxPoint;
}
};
我贴个我的算法吧，你贴个你的标准答案，比一下就好了,咱们思路差太多。
【在 i******s 的大作中提到】
: 忍不住替habbit说一句，如果枚举所有点，并且每次内循环前用新的hashmap的话，可
: 以只存斜率，因为此时之前一点已经固定(外层循环确定起始点)，所以可以用斜率做
: key。但是如果hashmap不是每次内循环前创建，而是在双重循序前创建，那么截距是一
: 定要的，光slope不够。还有这道题用slope有精度问题，
: 消除方法最简单就是换个直线表示方式，用Ax+By+C = 0。其中A, B和C都是整数，每两
: 个点构成的直线都这样表示，注意用gcd法保证A,B和C没有公约数，并且保证符号相
: 同(可以假设A永远是正)。而且这道题最大的trick是如何处理重复的点，一般没做过的
: 第一次做不一定想得到好办法。总体看之前的讨论无语了，跳出来说几句。
template <>
struct hash
{
typedef std::size_t result_type;
result_type operator()(const pair
{ return ((long)t.first * 1000003 + t.second )& (((long)1<<32 ) - 1);
}
};
}
class Solution {
public:
// suppose no two points are the same
int gcd(int a, int b)
{ return !b? a: gcd(b, a %b); }
pair
{
int x1 = points[pointI].x, y1 = points[pointI].y,
x2 = points[pointJ].x, y2 = points[pointJ].y;
int diffy = y1 - y2, diffx = x1 - x2;
if(diffy == 0 || diffx == 0)
{
if(diffy == 0) diffx = 1;
if(diffx == 0) diffy = 1;
return make_pair(diffy, diffx);
}
if(diffy < 0)
{
diffy = -diffy;
diffx = -diffx;
}
int gcdVal = gcd(abs(diffy), abs(diffx));
return make_pair(diffy/gcdVal, diffx/gcdVal);
}
bool samePoint(vector
{ return points[pointI].x == points[pointJ].x && points[pointI].y ==
points[pointJ].y; }
/*
string intToStr(int val)
{
if(!val) return "0";
string str = "";
while(val)
{
str += val %10 + '0';
val /= 10;
}
reverse(str.begin(), str.end());
return str;
}
string pairToStr(pair
{ return intToStr(p.first) + " " + intToStr(p.second);}
＊/
int maxPoints(vector
unordered_map
int maxPoint = 0;
for(int pointI = 0; pointI < points.size(); ++ pointI)
{
map.clear();
int sameCnt = 1, diffMax = 0;
for(int pointJ = 0; pointJ < points.size(); ++ pointJ)
{
if(pointI == pointJ) continue;
if(samePoint(points, pointI, pointJ))
{
++ sameCnt;
continue;
}
pair
if(map.find(kval) == map.end())
map[kval] = 1;
else
++map[kval];
diffMax = max(diffMax, map[kval]);
}
maxPoint = max(maxPoint, diffMax + sameCnt);
}
return maxPoint;
}
};
我贴个我的算法吧，你贴个你的标准答案，比一下就好了,咱们思路差太多。
【在 i******s 的大作中提到】
: 忍不住替habbit说一句，如果枚举所有点，并且每次内循环前用新的hashmap的话，可
: 以只存斜率，因为此时之前一点已经固定(外层循环确定起始点)，所以可以用斜率做
: key。但是如果hashmap不是每次内循环前创建，而是在双重循序前创建，那么截距是一
: 定要的，光slope不够。还有这道题用slope有精度问题，
: 消除方法最简单就是换个直线表示方式，用Ax+By+C = 0。其中A, B和C都是整数，每两
: 个点构成的直线都这样表示，注意用gcd法保证A,B和C没有公约数，并且保证符号相
: 同(可以假设A永远是正)。而且这道题最大的trick是如何处理重复的点，一般没做过的
: 第一次做不一定想得到好办法。总体看之前的讨论无语了，跳出来说几句。
i*s
169 楼
之前回的有误，请看我更正后的解答，你这样行是因为每次内循环前都clear了map。如
果换一个实现，则一定要存截距。anyway，slope的精度问题如果面试官死扣，那就只
能换Ax+By+C的表示方式，如果让过就过了。我碰到过both。
);
【在 h*******e 的大作中提到】
: namespace std {
: template <>
: struct hash >
: {
: typedef std::size_t result_type;
: result_type operator()(const pair & t) const
: { return ((long)t.first * 1000003 + t.second )& (((long)1<<32 ) - 1);
: }
: };
: }
果换一个实现，则一定要存截距。anyway，slope的精度问题如果面试官死扣，那就只
能换Ax+By+C的表示方式，如果让过就过了。我碰到过both。
);
【在 h*******e 的大作中提到】
: namespace std {
: template <>
: struct hash
: {
: typedef std::size_t result_type;
: result_type operator()(const pair
: { return ((long)t.first * 1000003 + t.second )& (((long)1<<32 ) - 1);
: }
: };
: }
h*e
170 楼
我的是check 了 Ａ＝０ Ｂ＝０的情况其实并不是严格意义上的斜率，垂直水平
是 ０， １ 和 １， ０ 一轴心点加上一方向自然能确定一条直线。
【在 i******s 的大作中提到】
: 之前回的有误，请看我更正后的解答，你这样行是因为每次内循环前都clear了map。如
: 果换一个实现，则一定要存截距。anyway，slope的精度问题如果面试官死扣，那就只
: 能换Ax+By+C的表示方式，如果让过就过了。我碰到过both。
:
: );
是 ０， １ 和 １， ０ 一轴心点加上一方向自然能确定一条直线。
【在 i******s 的大作中提到】
: 之前回的有误，请看我更正后的解答，你这样行是因为每次内循环前都clear了map。如
: 果换一个实现，则一定要存截距。anyway，slope的精度问题如果面试官死扣，那就只
: 能换Ax+By+C的表示方式，如果让过就过了。我碰到过both。
:
: );
i*s
171 楼
你的解法没问题，只是要记得为什么可以不保存截距，只用"斜率"就可以。有的面试官
会confuse，因为可能他们没有想过如果每次内循环前清了map(或者创建一个新的)，则
截距不是必须的。因为一个点在外循环是已确定。如果碰上绕不过的新手面试官，建议
保存截距以迎合他们的口味。。。
【在 h*******e 的大作中提到】
: 我的是check 了 Ａ＝０ Ｂ＝０的情况其实并不是严格意义上的斜率，垂直水平
: 是 ０， １ 和 １， ０ 一轴心点加上一方向自然能确定一条直线。
会confuse，因为可能他们没有想过如果每次内循环前清了map(或者创建一个新的)，则
截距不是必须的。因为一个点在外循环是已确定。如果碰上绕不过的新手面试官，建议
保存截距以迎合他们的口味。。。
【在 h*******e 的大作中提到】
: 我的是check 了 Ａ＝０ Ｂ＝０的情况其实并不是严格意义上的斜率，垂直水平
: 是 ０， １ 和 １， ０ 一轴心点加上一方向自然能确定一条直线。
p*e
172 楼
A,B,C的解法更局限一点吧，因为只适用于整数情况
如果点是浮点的话，还是要考虑精度问题
【在 i******s 的大作中提到】
: 之前回的有误，请看我更正后的解答，你这样行是因为每次内循环前都clear了map。如
: 果换一个实现，则一定要存截距。anyway，slope的精度问题如果面试官死扣，那就只
: 能换Ax+By+C的表示方式，如果让过就过了。我碰到过both。
:
: );
如果点是浮点的话，还是要考虑精度问题
【在 i******s 的大作中提到】
: 之前回的有误，请看我更正后的解答，你这样行是因为每次内循环前都clear了map。如
: 果换一个实现，则一定要存截距。anyway，slope的精度问题如果面试官死扣，那就只
: 能换Ax+By+C的表示方式，如果让过就过了。我碰到过both。
:
: );
i*s
173 楼
well, 一般遇到的都是point是int x, int y。如果面试官扣这个，那就只有跟他聊聊
怎么解决精度问题了。但对于都是int的情况，ABC法比较好。
【在 p****e 的大作中提到】
: A,B,C的解法更局限一点吧，因为只适用于整数情况
: 如果点是浮点的话，还是要考虑精度问题
怎么解决精度问题了。但对于都是int的情况，ABC法比较好。
【在 p****e 的大作中提到】
: A,B,C的解法更局限一点吧，因为只适用于整数情况
: 如果点是浮点的话，还是要考虑精度问题
h*e
174 楼
浮点要考虑精度问题的而且这时候要重写 unordered_map的equal函数了， 我现在还
没想清楚为什么这个 哈希函数一定要外面加个namespace std才能通过。
这种template我之前也没见过 搜了一下发现叫做全特化模板。
【在 p****e 的大作中提到】
: A,B,C的解法更局限一点吧，因为只适用于整数情况
: 如果点是浮点的话，还是要考虑精度问题
没想清楚为什么这个 哈希函数一定要外面加个namespace std才能通过。
这种template我之前也没见过 搜了一下发现叫做全特化模板。
【在 p****e 的大作中提到】
: A,B,C的解法更局限一点吧，因为只适用于整数情况
: 如果点是浮点的话，还是要考虑精度问题
h*e
175 楼
轴心点 pointI 给定了 知道了 Ａ Ｂ就能知道 C了所以两个值就够了
【在 i******s 的大作中提到】
: 之前回的有误，请看我更正后的解答，你这样行是因为每次内循环前都clear了map。如
: 果换一个实现，则一定要存截距。anyway，slope的精度问题如果面试官死扣，那就只
: 能换Ax+By+C的表示方式，如果让过就过了。我碰到过both。
:
: );
【在 i******s 的大作中提到】
: 之前回的有误，请看我更正后的解答，你这样行是因为每次内循环前都clear了map。如
: 果换一个实现，则一定要存截距。anyway，slope的精度问题如果面试官死扣，那就只
: 能换Ax+By+C的表示方式，如果让过就过了。我碰到过both。
:
: );
f*t
176 楼
struct Point {
int x;
int y;
Point() : x(0), y(0) {}
Point(int a, int b) : x(a), y(b) {}
};
class Solution {
static int gcd(int x, int y) {
while (y != 0) {
int temp = y;
y = x % y;
x = temp;
}
return x;
}
void Simplify(pair &pr) {
if (pr.first == 0 && pr.second == 0) {
return;
}
int z = Solution::gcd(pr.first, pr.second);
pr.first /= z;
pr.second /= z;
}
struct PairHash {
size_t operator() (const pair &pr) const {
return pr.first * 97 + pr.second;
}
};
public:
int maxPoints(vector &points) {
if (points.empty()) {
return 0;
}
int res = 0;
unordered_map, int, PairHash> um;
for (size_t i = 0; i + res < points.size(); ++i) {
for (size_t k = i + 1; k < points.size(); ++k) {
auto pr = make_pair(points[k].x - points[i].x,
points[k].y - points[i].y);
Simplify(pr);
++um[pr];
}
for (auto item : um) {
if (res < item.second) {
res = item.second;
}
}
um.clear();
}
return 1 + res;
}
};
int x;
int y;
Point() : x(0), y(0) {}
Point(int a, int b) : x(a), y(b) {}
};
class Solution {
static int gcd(int x, int y) {
while (y != 0) {
int temp = y;
y = x % y;
x = temp;
}
return x;
}
void Simplify(pair
if (pr.first == 0 && pr.second == 0) {
return;
}
int z = Solution::gcd(pr.first, pr.second);
pr.first /= z;
pr.second /= z;
}
struct PairHash {
size_t operator() (const pair
return pr.first * 97 + pr.second;
}
};
public:
int maxPoints(vector
if (points.empty()) {
return 0;
}
int res = 0;
unordered_map
for (size_t i = 0; i + res < points.size(); ++i) {
for (size_t k = i + 1; k < points.size(); ++k) {
auto pr = make_pair(points[k].x - points[i].x,
points[k].y - points[i].y);
Simplify(pr);
++um[pr];
}
for (auto item : um) {
if (res < item.second) {
res = item.second;
}
}
um.clear();
}
return 1 + res;
}
};
w*a
177 楼
这个用分数存key最好，但是要写个GCD做约分
w*a
178 楼
感觉这题的考点就是用分数作为KEY
相关阅读
当Meehu遭遇愤怒的小鸟我要考虑是不是要加固窗户了...为什么亲密时刻她对我这么做？Jacob的脚垫又破了！奔一下病娃发现一个潜在喵星红人请教一个关于猫猫眼睛的问题（6楼更新图最后的努力：请一起来阻止活取熊胆的归真堂上市！年糕的猫妈周记（一）主银尼看窝的新衣服，口爱嘛. (转载)yidingjizhu 封 YesYouAre 在 pets 版 (转载)猫儿有时做出呕吐状，还带咳嗽，是怎么回事【猫奴的烦恼】踩奶也要有个限度！！！发个跟pet无关的啊自制自动猫玩具一枚，成本1美元大家看到艾迪妈在十大的帖子了么？我在dog sitter小布猜猜这是什么？最近总觉得跟孩子没什么交流南瓜这几天可怜兮兮的。。。