基于随机增量法的高效结构构建技术

概述&＃xff1a;在解决前 $n-1$ 规模的问题前提之下&＃xff0c;使得第$n$ 个新加入的元素也是符合条件的
注意&＃xff1a;结合随机化&＃xff0c;积累构造法则
例子&＃xff1a;扩展KMP&＃xff0c;最小圆覆盖

• 要素&＃xff1a;三层循环

引理&＃xff1a; 证明在这里

1&＃xff0c;最小圆覆盖在确定其中点的情况下唯一确认
2&＃xff0c;若是第 $i$ 个点不在前面点的最小圆覆盖上&＃xff0c;那么一定在可能的圆的边界上

步骤&＃xff1a;

1. 随机化点集
2. 初始时一个点的最小覆盖圆就是这个点本身
3. 假设已经求出前$i-1$个点的最小覆盖圆
4. 若第 $i$ 个点在圆内&＃xff0c;则跳过;
5. 若第 $i$ 个点不在圆内&＃xff0c;根据性质2&＃xff0c;只需要找出一个圆覆盖前$i-1$个点&＃xff0c;且第$i$个点在圆边上
6. 由于三点确定一个圆&＃xff0c;继续找第二个点j&＃xff0c;类似于性质2&＃xff0c;现在需要找出一个圆覆盖前$j-1$个点&＃xff0c;且第$i$和第$j$个点在圆上
7. 最后找第三个点$k$&＃xff0c;同样现在需要找出一个圆覆盖前$k-1$个点&＃xff0c;且第$i$和第$j$和第$k$个点在圆边上&＃xff08;那么说明&＃xff0c;只要发现不在里面&＃xff0c;那么圆就得适应新的点&＃xff0c;保证前面的已经实现&＃xff0c;所以不需要考虑条件限制&＃xff09;

pair<pdd,pdd> get_line(pdd a,pdd b)
{return {(a&＃43;b)/2,spin(b-a,PI/2)};///第一位端点&＃xff0c;第二维方向
}node get_node(pdd a,pdd b,pdd c)
{auto u &＃61; get_line (a,b);auto v &＃61; get_line (a,c);auto p &＃61; get_line_join(u.x,u.y,v.x,v.y);return {p,get_dist(p,a)};
}int main()
{scanf("%d", &n);for (int i &＃61; 0; i < n; i &＃43;&＃43; ) scanf("%lf%lf", &q[i].x, &q[i].y);random_shuffle(q, q &＃43; n);node c &＃61; {q[0],0};for(int i&＃61;1;i<n;i&＃43;&＃43;){if(dcmp(c.r,get_dist(c.p,q[i]))<0){c &＃61; {q[i],0};for(int j&＃61;0;j<i;j&＃43;&＃43;){if(dcmp(c.r,get_dist(c.p,q[j]))<0){c &＃61; {(q[i] &＃43; q[j]) / 2, get_dist(q[i], q[j]) / 2};for(int k&＃61; 0;k<j;k&＃43;&＃43;){if(dcmp(c.r,get_dist(c.p,q[k]))<0)c &＃61; get_node(q[i],q[j],q[k]);}}}}}printf("%.10lf\n", c.r);printf("%.10lf %.10lf\n", c.p.x, c.p.y);
}