Finding Lines
Problem's Link: http://acm.hnu.cn/online/?action=problem&type=show&id=13348&courseid=0
Mean:
给你平面上1e5个点，让你判断是否可以找到一条直线，使得p%的点都在这条直线上。
analyse:
经典的随机算法题。
每次随机出两个点，然后对n个点进行判断，看是否有p%的点在这条直线上。
关于随机算法正确性的证明：
每次随机一个点，这个点在直线上的概率是p，p最小为20%；
随机两个点来确定一条直线，那么随机一条直线的概率就是p*p，即:4%；
也就是说，在直线上概率为0.04，不在的概率为1-0.04=0.96;
那么随机k次不在直线上的概率为0.96^k，也就是答案出现误差的概率。
这题我们随机1000次，错误的概率接近1e-18，基本是不可能事件，证毕.
Time complexity: O()
Source code:
;
; ) ;
) ;
;
;
;
; ;
}
/*
*/
另外一种据说更高效的解法：
;
;
;
)
;
;
; )
;
; s ; ; ;
;
}
再附上一种二分的做法：
;
)
;
) ; ;
; || ;
}