b*****i
发帖数: 130 | 1 面经里看到的，google不到思路，只好求助各位了。
题目： 平面N个点，找两点连线正好把点分到两半。 |
l*********8
发帖数: 4642 | 2 以x坐标最小的一个点为原点，转换成极坐标。 然后找另外一个点与原点连线。
【在 b*****i 的大作中提到】
: 面经里看到的，google不到思路，只好求助各位了。
: 题目： 平面N个点，找两点连线正好把点分到两半。
|
y***n
发帖数: 1594 | |
l*****a
发帖数: 14598 | 4 一个点与其他n-1点分别连线，
考虑与x 轴的角度，从小到大排序,找中间的
需注意多点同线的情况
【在 y***n 的大作中提到】
: 能不能再解释一下。
|
z*t
发帖数: 13 | 5 #include
struct point{double x, double y;};
void split(vector & v, point & line_point1, point & line_point2){
int n = v.size();
if(n==2){
line_point1 = v[0];
line_point2 = v[1];
return;
}
//get left most point
int left_index = 0;
for(int i=1;i
if(v[i].x
left_index = i;
}
//transform to angle
// angle and array index
vector > angle(n-1);
for(int i=0;i
if(i==left_index)
continue;
if(v[i].x == v[left_index].x)
//+oo -oo
angle.push_back({v[i].y > v[left_index].y ? numeric_limit::
max() : numeric_limit::min(), i });
else
angle.push_back( {(v[i].y - v[left_index].y) / (v[i].x - v[left_index]
.x), i} );
}
//get median index of angle
//TODO O(n) median select algo.
sort(begin(angle), end(begin));
line_point1 = v[left_index];
//n is odd/even
line_point2 = v[angle[n/2 - 1].second];
} |
z*t
发帖数: 13 | |
z*t
发帖数: 13 | 7 stackoverflow里给出的那个随机算法很有意思 |
r****s
发帖数: 1025 | 8 那是computational geometry的算法，和combinatorial optimization（求多项式最优
解）一样都是CS graduate level的课程。stackoverflow的那哥们正在读研估计。 |
