z****e
发帖数: 54598 | 1 2d平面上一堆的点，要求取其中两点连线
然后正好一半的点在这条线的同侧 |
c**1
发帖数: 71 | 2 this works when no 3 points in the same line, and of course total number of
points is even.
find the point with lowest Y, break tie by choosing lowest X. name it a
for each other point b, calculate the angle between line ab and x axis
c is the median of all other points by comparing the angle, ac is what you
want.
O(n) |
c**1
发帖数: 71 | 3 and there might be no solution at all if existing 3 points in a line, even
when total number is even. think the extreme case when all 2k+2 points are
on the same line. |
z****e
发帖数: 54598 | 4 soga
接包子八
even
are
【在 c**1 的大作中提到】
: and there might be no solution at all if existing 3 points in a line, even
: when total number is even. think the extreme case when all 2k+2 points are
: on the same line.
|
c**1
发帖数: 71 | 5 what is 包子? how can I check how many 包子 I have?
I always hear people talking about 包子, but never know what it means :) |
u*****o
发帖数: 1224 | 6 哇塞，果真是重赏之下必有勇夫。。这招好啊
of
you
【在 c**1 的大作中提到】
: this works when no 3 points in the same line, and of course total number of
: points is even.
: find the point with lowest Y, break tie by choosing lowest X. name it a
: for each other point b, calculate the angle between line ab and x axis
: c is the median of all other points by comparing the angle, ac is what you
: want.
: O(n)
|
c********e
发帖数: 186 | 7 想问一下正好一半的点在这条线的同侧是什么意思？
在这条线的上点怎算哪边还是哪边都不算？
【在 z****e 的大作中提到】
: 2d平面上一堆的点，要求取其中两点连线
: 然后正好一半的点在这条线的同侧
|
c********e
发帖数: 186 | 8 如果a点（bottom left那个点）与b，c在同一直线上，那我们通过这方法找不到直线，
但是有另外的线不通过a会符合要求啊
of
you
【在 c**1 的大作中提到】
: this works when no 3 points in the same line, and of course total number of
: points is even.
: find the point with lowest Y, break tie by choosing lowest X. name it a
: for each other point b, calculate the angle between line ab and x axis
: c is the median of all other points by comparing the angle, ac is what you
: want.
: O(n)
|
f*******b
发帖数: 520 | 9
是的，所以楼上的方法正确的先决条件是：3点不一线+点数even
【在 c********e 的大作中提到】
: 如果a点（bottom left那个点）与b，c在同一直线上，那我们通过这方法找不到直线，
: 但是有另外的线不通过a会符合要求啊
:
: of
: you
|
c********e
发帖数: 186 | 10 可是原题无这个条件，也就是说这个方法不能解决原题，只能解决的原题特殊情况，我
的理解对吗？
【在 f*******b 的大作中提到】
:
: 是的，所以楼上的方法正确的先决条件是：3点不一线+点数even
|
|
|
z*******3
发帖数: 13709 | 11 为了这题还去看了下cross product的direction的expression
人生真悲剧 |
p****n
发帖数: 148 | 12 若稍改一下，是不是总有解了，即使是有三（或多）点共线
2d平面上一堆的点，要求取其中两点连线
使这条线的两侧的点数相同
even
are
【在 c**1 的大作中提到】
: and there might be no solution at all if existing 3 points in a line, even
: when total number is even. think the extreme case when all 2k+2 points are
: on the same line.
|
m********s
发帖数: 55301 | 13 你当下有12个包子。
回答这个可以得一个包子吧？
登陆、家页、金融中心。
what is 包子?
【在 c**1 的大作中提到】
: what is 包子? how can I check how many 包子 I have?
: I always hear people talking about 包子, but never know what it means :)
|
c**1
发帖数: 71 | |
m********s
发帖数: 55301 | 15 哦，发财了。
谢谢
sent
【在 c**1 的大作中提到】
: sent
|
