• Welcome to the world's largest Chinese hacker forum

    Welcome to the world's largest Chinese hacker forum, our forum registration is open! You can now register for technical communication with us, this is a free and open to the world of the BBS, we founded the purpose for the study of network security, please don't release business of black/grey, or on the BBS posts, to seek help hacker if violations, we will permanently frozen your IP and account, thank you for your cooperation. Hacker attack and defense cracking or network Security

    business please click here: Creation Security  From CNHACKTEAM

Recommended Posts

发布时间: 2022-02-06 11:5933335

基本内容链接

更新:

最小圆覆盖

震惊我一年的随机增量法.

定理1:如果第(I)个点不在第(i-1)个点的最小圆覆盖(C)中,那么这个点一定在第(I)个点的最小圆覆盖上。

根据这个定理,我们有这样一种做法:

c;

for(i=1到n)

{

如果(P不在C中)

{

C={P,0 };

对于(j=1至i-1)

{

如果(P[j]不在C中)

{

C={0.5*(P P[j]),0.5*dist(P,P[j])};

for(k=1至j-1)

{

如果(P[k]不在C中)

{

C=外接圆(P,P[j],P[k]);

}

}

}

}

}

}

求外接圆可以直接求两边垂线的交点。

考虑这种方法的复杂性:

最后只有\(3\)个点决定一个圆,所以每个点决定这个圆的概率只有\(\frac{3}{n}\),所以每个层循环在\(i\)位置调用下一层的概率最高\(\frac{3}{i}\),但是

\[\begin{aligned}

t1(n)=0(n)\sum_{i=1}^n\frac{3}{i}t_2(i)\\

T2(n)=o(n)\sum_{i=1}^n\frac{3}{i}t_3(i)\\

T3(n)=O(n)

\ end {对齐}

\]

\(t1(n)=T2(n)=T3(n)=O(n)\)即可求解。

Link to comment
Share on other sites