面试（54）
问题描述：
设rand（s，t）返回[s,t]之间的随机小数，利用该函数在一个半径为R的圆内找随机n个点，并给出时间复杂度分析。
在半径为R的圆内找随机的n个点，既然是找点，那么就需要为其建立坐标系，如果建立平面直角坐标系，以圆心为原点，建立半径为R的圆的直角坐标系。要使随机的点在圆内，则必须使其所找的点 point 的x，y坐标的绝对值小于R，问题转化为：随机的找n个圆内的点，使其x，y坐标的绝对值均小于R。这里以x为例， 首先 x 应满足 -R&= x &= R； &y同理。这样产生的点均在以圆心为中心，边长为2R的正放形内，需要另外判断其距离R的值。本文介绍采用极坐标的形式，建立圆的极坐标系，则圆内的任意一点满足&P(ρ,θ)（用ρ表示线段OP的长度，θ表示从Ox到OP的角度angle），此时问题转化为：找一点，使其到圆心的距离OP大于等于0
小于R，极角大于等于0 小于360，则OP=rand(0, R) ，当 OP== R 时重新寻找，angle = rand(0,360) ，当angle==360时，重新寻找。每找到一个点p，将其与之前所找到的所有点进行比较，若重合，则继续寻找，否则将其加入到已找到的点集合中，直到找到n个点。
存放点的数据结构
typedef struct Point{
算法流程：
for( i= i &0; i--)
& &产生 p.r = rand(0,R)，且p.r != R
& &产生 p.rangle = rand(0,360) ,且 p.rangle != 360
& &遍历所有产生的点，若 p 已经存在，则重新生成该点
& &否则将其加入到产生的点集合中
生成第n个点，需要先遍历前n-1个点，时间复杂度为O(n)，故生成n个点的时间复杂度为O(n^2)
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：89826次
积分：1817
积分：1817
排名：第17892名
原创：84篇
转载：78篇
(2)(1)(4)(1)(1)(20)(43)(9)(2)(2)(7)(24)(26)(20)