关键词:
原文链接 https://www.cnblogs.com/cly-none/p/loj2159.html
题意:给出(n)个点,你需要按编号将其划分成不超过(m)段连续的区间,使得所有每个区间的最小圆覆盖的半径的最大值最小。输出这个最小化的最大值和方案(圆心)。
(n,m leq 10^5)
显然要二分答案。然后,一个区间就是越长越好。
首先,考虑最小圆覆盖(O(n))的随机增量法,但为了保证复杂度,我们需要能够random_shuffle
。如果直接按照编号顺序添加点,时间复杂度会是(O(n^3 log n))的。
为了能够random_shuffle
,我们不能一个个添加结点,而是在一开始就知道要对哪些点求最小圆覆盖。
一个思路是二分区间长度。因为有(m)段区间,所以这么做是(O(nm log^2 n))的。并不优秀,在数据水的情况下还不如上一种做法。
为何二分的复杂度不优秀?在于它没有利用所有区间长度和是(n)这一性质,也就是二分的上界太大了。
于是我们可以考虑增加区间长度。一个套路是分块。不断增加(sqrt n)的长度,到不行时再改为增加(1)的长度。这样在这个区间长度为(l)的情况下,复杂度是(O(l sqrt l))的。于是就得到了(O(n sqrt n log n))的做法。
然而实际上倍增就好了。分为两步,首先,我们找到答案二进制下最高的一位,然后,向下确定每一位。这样,对于一个长度为(l)的区间,我们要做(log l)最小圆覆盖,每次要处理的点的个数都是不超过(2l)的。因此,这个区间的复杂度就是(O(l log l)),总复杂度为(O(n log^2 n)),可以通过本题。
#include <bits/stdc++.h>
using namespace std;
#define gc() getchar()
template <typename tp>
inline void read(tp& x)
x = 0; char tmp; bool key = 0;
for (tmp = gc() ; !isdigit(tmp) ; tmp = gc())
key = (tmp == '-');
for ( ; isdigit(tmp) ; tmp = gc())
x = (x << 3) + (x << 1) + (tmp ^ '0');
if (key) x = -x;
typedef double db;
const db eps = 1e-8;
inline int jud(db x)
return x > -eps ? x > eps ? 1 : 0 : -1;
struct point
db x,y;
point(db x_=0, db y_=0): x(x_), y(y_)
point operator + (const point& a) const
return point(x + a.x, y + a.y);
point operator - (const point& a) const
return point(x - a.x, y - a.y);
db abs() const
return sqrt(x * x + y * y);
db norm() const
return x * x + y * y;
point perp() const
return point(- y, x);
point operator * (const db& a) const
return point(x * a, y * a);
;
db cross(point a,point b)
return a.x * b.y - a.y * b.x;
db dot(point a,point b)
return a.x * b.x + a.y * b.y;
point unit(point a)
db d = a.abs();
a.x /= d;
a.y /= d;
return a;
struct line
point u,v;
line(point u_=point(), point v_=point()): u(u_)
v = unit(v_);
;
db dis(point a,line b)
return cross(a - b.u, b.v);
point inse(line a,line b)
assert(jud(cross(a.v, b.v)) != 0);
db d = dis(a.u, b) / cross(a.v, b.v);
return a.u - (a.v * d);
struct circle
point o;
db r;
circle(point o_=point(), db r_ = 0): o(o_), r(r_)
;
circle circum(point a,point b,point c)
line l1 = line((a + b) * (0.5), (a - b).perp());
line l2 = line((b + c) * (0.5), (b - c).perp());
point d = inse(l1,l2);
return circle(d, (a - d).abs());
const int N = 100010;
int n,m,cnt,num;
point po[N], ans[N], tmp[N];
bool check(int l,int r,db x)
for (int i = l ; i <= r ; ++ i)
tmp[i] = po[i];
random_shuffle(tmp+l,tmp+r+1);
circle cir = circle(tmp[l], 0);
for (int i = l+1 ; i <= r ; ++ i)
if (jud(cir.r - (tmp[i] - cir.o).abs()) >= 0);
else
cir = circle(tmp[i], 0);
for (int j = l ; j < i ; ++ j)
if (jud(cir.r - (tmp[j] - cir.o).abs()) >= 0);
else
cir = circle((tmp[i] + tmp[j]) * (0.5), (tmp[i] - tmp[j]).abs() * 0.5);
for (int k = l ; k < j ; ++ k)
if (jud(cir.r - (tmp[k] - cir.o).abs()) >= 0);
else cir = circum(tmp[i], tmp[j], tmp[k]);
ans[cnt] = cir.o;
return jud(x - cir.r) >= 0;
bool doit(db x)
cnt = 1;
for (int lp = 1, len ; lp <= n ; lp += len, ++ cnt)
for (len = 1 ; lp + (len<<1) - 1 <= n && check(lp, lp + (len << 1) - 1, x) ; len <<= 1);
for (int i = (len >> 1) ; i >= 1 ; i >>= 1)
if (lp + len + i - 1 <= n && check(lp, lp + len + i - 1, x)) len += i;
check(lp, lp + len - 1, x);
-- cnt;
return cnt <= m;
int main()
read(n), read(m);
for (int i = 1, x, y ; i <= n ; ++ i)
read(x), read(y);
po[i] = point(x, y);
db l = 0, r = 2000000, mid;
while (r - l > 1e-8)
mid = (l + r) / 2.0;
if (doit(mid)) r = mid;
else l = mid;
printf("%.7lf
",r);
doit(r);
printf("%d
",cnt);
for (int i = 1 ; i <= cnt ; ++ i)
printf("%.7lf %.7lf
", ans[i].x, ans[i].y);
return 0;
小结:本题反应了倍增的特性。也就是每次需要判断的大小和答案大小是同一级别的。因此,在(O(ANS))判断一个答案的合法性时,可以用倍增替代二分来保证复杂度。
最小圆覆盖
1structPoint{doublex,y;};2structCircle{Pointc;doubler;};3doubledist(Pointa,Pointb){4returnsqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));5}6Circlecalc(Pointp1,Pointp2,Pointp3){7Circletemp;8doublea,b,c, 查看详情
做题记录
多项式编号问题算法5644分治NTT+容斥4705数组1~k次幂和NTT+多项式求逆4723常系数齐次线性递推多项式取模3824常系数齐次线性递推多项式取模数学编号问题算法4827斯特林数(k次方)cf960g前缀max个数,后缀max个数斯特林数cf961g斯特... 查看详情
java案例:最小覆盖圆问题
文章目录一、提出任务-最小覆盖圆(一)描述(二)输入(三)输出(四)样例输入输出二、完成任务(一)编程思路(二)编写代码,实现功能(三)运行程序,查看结果一、提出任务-最小覆盖圆(一)描述给出平面上N(N≤1... 查看详情
java案例:最小覆盖圆问题
文章目录一、提出任务-最小覆盖圆(一)描述(二)输入(三)输出(四)样例输入输出二、完成任务(一)编程思路(二)编写代码,实现功能(三)运行程序,查看结果一、提出任务-最小覆盖圆(一)描述给出平面上N(N≤1... 查看详情
java案例:最小覆盖圆问题
文章目录一、提出任务-最小覆盖圆(一)描述(二)输入(三)输出(四)样例输入输出二、完成任务(一)编程思路(二)编写代码,实现功能(三)运行程序,查看结果一、提出任务-最小覆盖圆(一)描述给出平面上N(N≤1... 查看详情
最小圆覆盖
求一个半径最小的圆使其内部至少包含m个点#include<bits/stdc++.h>usingnamespacestd;#defineMn305constdoubleeps=1e-7;constdoublepi=acos(-1.0);structPoint doublex,y; Point() Point(doubletx,doublety) x=tx; y=ty; 查看详情
mapletrees(最小覆盖圆)
MapletreesTimeLimit:1000/1000MS(Java/Others)MemoryLimit:32768/32768K(Java/Others)TotalSubmission(s):222AcceptedSubmission(s):79 ProblemDescriptionTherearealotoftreesinHDU.Kikiwanttosurroundallthe 查看详情
luogup1742最小圆覆盖(代码片段)
最小圆覆盖主要是我太菜了不会证明qwq,上面的博客讲的非常好。主要是存代码:#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>#include<cmath>usingnamespacestd;constintN=100009;constdoublee 查看详情
p1742最小圆覆盖(代码片段)
(color#0066ff题目描述)给出N个点,让你画一个最小的包含所有点的圆。(color#0066ff输入格式)先给出点的个数N,2<=N<=100000,再给出坐标Xi,Yi.(-10000.0<=xi,yi<=10000.0)(color#0066ff输出格式)输出圆的半径,及圆心的坐标,保留10位小数(c... 查看详情
[balkan2002]alien最小圆覆盖(代码片段)
传送门期望(O(n))的神奇算法代码:#include<cstdio>#include<iostream>#include<algorithm>#include<cmath>usingnamespacestd;voidread(int&x)charch;boolok;for(ok=0,ch=getchar();!isdigit(ch);ch=getchar())if(ch=='-')ok=1;for(x=0;isdigit(ch);x=x*10+ch-'0'... 查看详情
c案例:最小覆盖圆问题(代码片段)
文章目录一、提出任务-最小覆盖圆(一)描述(二)输入(三)输出(四)样例输入输出二、完成任务(一)编程思路(二)编写代码,实现功能(三)运行程序,查... 查看详情
c案例:最小覆盖圆问题(代码片段)
文章目录一、提出任务-最小覆盖圆(一)描述(二)输入(三)输出(四)样例输入输出二、完成任务(一)编程思路(二)编写代码,实现功能(三)运行程序,查... 查看详情
最小圆覆盖gym-102006i(代码片段)
#include<bits/stdc++.h>#defineLLlonglong#definefifirst#definesesecond#definemkmake_pair#definePLLpair<LL,LL>#definePLIpair<LL,int>#definePIIpair<int,int>#defineSZ(x)((int)x.size())#defineullunsignedlonglongusingnamespacestd;constintN=2e5+7;constintinf=0x3f3f3f3f;constLLINF=0x... 查看详情
c案例:最小覆盖圆问题(代码片段)
文章目录一、提出任务-最小覆盖圆(一)描述(二)输入(三)输出(四)样例输入输出二、完成任务(一)编程思路(二)编写代码,实现功能(三)运行程序,查... 查看详情
bzoj1336[balkan2002]alien最小圆覆盖随机增量法
【BZOJ1336】[Balkan2002]Alien最小圆覆盖Description给出N个点,让你画一个最小的包含所有点的圆。Input先给出点的个数N,2<=N<=100000,再给出坐标Xi,Yi.(-10000.0<=xi,yi<=10000.0)Output输出圆的半径,及圆心的坐标SampleInput68.09.04.07.51.02.05.... 查看详情
hdu3007最小圆覆盖-随机增量法
#include<iostream>#include<cstdio>#include<cmath>#include<algorithm>usingnamespacestd;constintN=505;intn;doubler;structdiandoublex,y;dian(doubleX=0,doubleY=0)x=X,y=Y;dianope 查看详情
bzoj1336/1337/2823[balkan2002]alien最小圆覆盖随机增量法
题目描述给出N个点,让你画一个最小的包含所有点的圆。输入先给出点的个数N,2<=N<=100000,再给出坐标Xi,Yi.(-10000.0<=xi,yi<=10000.0)输出输出圆的半径,及圆心的坐标样例输入68.09.04.07.51.02.05.18.79.02.04.51.0样例输出5.005.005.00题... 查看详情
[poi2011]lightningconductor
题面在这里description已知一个长度为\(n\)的序列\(a_1,a_2,...,a_n\)。对于每个\(1\lei\len\),找到最小的非负整数\(p\),满足对于任意的\(1\lej\len\),\(a_j\lea_i+p-\sqrt|i-j|\)datarange\[n\le5\times10^5,a_i\le10^9\]solution绝对值怎么办?我们先从左到右\(DP\j 查看详情