正文

[matlab]10.最小覆盖圆(代码片段)

clemente  clemente  2022-12-28  301

关键词：

clear all;
close all;
clc;

n=100;
p=rand(n,2);

p1=p(1,:); %取第一行的值 P1点
p2=p(2,:); %取第二行的值 P2点
r=sqrt((p1(1)-p2(1))^2+(p1(2)-p2(2))^2)/2; %求两点半径
cenp=(p1+p2)/2;   %求两点中点

for i=3:n
    newp=p(i,:);    %从第三行开始 储存新的点
    d=sqrt((cenp(1)-newp(1))^2+(cenp(2)-newp(2))^2);  %圆心到新的点的距离为d
    if d>r %当距离大于现有半径的时候,赋值更大的半径
        r=(r+d)/2;
        cenp=cenp+(d-r)/d*(newp-cenp); %按比例位移中心
    end    
end

hold on;
plot(p(:,1),p(:,2),‘rs‘);
x0=cenp(1); %圆心横坐标
y0=cenp(2); 
theta=0:0.01:2*pi;
x=x0+r*cos(theta);
y=y0+r*sin(theta);
plot(x,y,‘k-‘,x0,y0,‘k.‘);
axis equal

最小覆盖圆

技术分享图片

bzoj1337最小圆覆盖(代码片段)

bzoj1337最小圆覆盖补充一个求三角形外心的向量法.用了点积的几何意义,很实用.出处.使用随机增量法求.首先随机打乱顺序,然后三重循环,选择当前在圆外的点更新圆,分别按照(1/2/3)个点确定圆的方式更新即可.由于随机一个点不在... 查看详情

luogup1742最小圆覆盖(代码片段)

最小圆覆盖主要是我太菜了不会证明qwq，上面的博客讲的非常好。主要是存代码：#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>#include<cmath>usingnamespacestd;constintN=100009;constdoublee 查看详情

c案例：最小覆盖圆问题(代码片段)

文章目录一、提出任务-最小覆盖圆（一）描述（二）输入（三）输出（四）样例输入输出二、完成任务（一）编程思路（二）编写代码，实现功能（三）运行程序，查... 查看详情

c案例：最小覆盖圆问题(代码片段)

java案例：最小覆盖圆问题

文章目录一、提出任务-最小覆盖圆（一）描述（二）输入（三）输出（四）样例输入输出二、完成任务（一）编程思路（二）编写代码，实现功能（三）运行程序，查看结果一、提出任务-最小覆盖圆（一）描述给出平面上N(N≤1... 查看详情

java案例：最小覆盖圆问题

模板最小圆覆盖——bzoj1336(代码片段)

博客链接https://blog.csdn.net/commonc/article/details/52291822#include<bits/stdc++.h>usingnamespacestd;#defineN100005typedefdoubledb;constdbeps=1e-10;constdbpi=acos(-1);intsign(dbk)if(k>eps)return1;elseif(k<-eps)return-1;return0;intcmp(dbk1,dbk2)returnsign(k1-k2);intinmid(dbk1,dbk2,d... 查看详情

[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'... 查看详情

做题poi2011r1-plot——最小圆覆盖&倍增(代码片段)

...将其划分成不超过(m)段连续的区间，使得所有每个区间的最小圆覆盖的半径的最大值最小。输出这个最小化的最大值和方案（圆心）。(n,mleq10^5)显然要二分答案。然后，一个区间就是越长越好。首先，考虑最小圆覆盖(O(n))的随机... 查看详情

覆盖点问题总结(代码片段)

1.最小的包围圆，将所有的点包围起来。（hdu3932）最小覆盖圆算法地址：http://soft.cs.tsinghua.edu.cn/blog/?q=node/1066问题的背景提出：考察固定在工作平台上的一直机械手，要捡起散落在不同位置的多个零件，并送到别的地方。那么，... 查看详情

bzoj2823:[ahoi2012]信号塔&&1336:[balkan2002]alien最小圆覆盖&&1337:最小圆覆盖(代码片段)

首先我写了个凸包就溜了这是最小圆覆盖问题，今晚学了一下先随机化点，一个个加入假设当前圆心为o，半径为r，加入的点为i若i不在圆里面，令圆心为i，半径为0再重新从1~i-1不停找j不在圆里面，令圆心为ij中点，直径为ij距... 查看详情

最小圆覆盖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... 查看详情

p1742最小圆覆盖(代码片段)

(color#0066ff题目描述)给出N个点，让你画一个最小的包含所有点的圆。(color#0066ff输入格式)先给出点的个数N,2<=N<=100000，再给出坐标Xi,Yi.(-10000.0<=xi,yi<=10000.0)(color#0066ff输出格式)输出圆的半径，及圆心的坐标，保留10位小数(c... 查看详情

p1742最小圆覆盖（计算几何）(代码片段)

体验过(O(n^3))过(10^5)吗？快来体验一波当(wys)的快感吧(QAQ)前置芝士1：二元一次方程组求解设[egincasesa1*x+b1*y=c1\a2*x+b2*y=c2endcases]（其中(a1,a2,b1,b2,c1,c2)为已知量）由(②)式得：[x=fracc2-b2*ya2]带入(①)式并化简得：[y=fracc1-fraca1*c2a2b1-frac... 查看详情

最小圆覆盖

求一个半径最小的圆使其内部至少包含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 查看详情

最小圆覆盖

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, 查看详情