关键词:
文章目录
一、提出任务 - 最小覆盖圆
(一)描述
- 给出平面上 N ( N ≤ 1 0 2 ) N(N\\le10^2) N(N≤102)个点。请求出一个半径最小的圆覆盖住所有的点。
(二)输入
- 第一行给出数字 N N N,接下来 N N N行,每行两个实数 x , y x,y x,y表示其坐标。其中, − 1 0 5 ≤ x , y ≤ 1 0 5 -10^5\\le x,y \\le 10^5 −105≤x,y≤105
(三)输出
- 第一行输出最小覆盖医的圆心
- 第二行输出半径
- 输出保留三位小数
(四)样例
输入
4
1 0
0 1
0 -1
-1 0
输出
0.000 0.000
1.000
二、完成任务
(一)编程思路
- 任意两点间距离的最大值就是最小覆盖圆的直径
- 距离最大值的两个点的中心就是最小覆盖圆的圆心
(二)编写代码,实现功能
- 在
C_WORK
目录里创建C程序 -最小覆盖圆.c
#include "stdio.h"
#include "math.h"
int main()
int n;
double distance, maxDistance = 0;
double cx = 0, cy = 0, r;
// 输入点数量
scanf("%d", &n);
// 声明点坐标数组
double x[n], y[n];
// 输入全部点的坐标
for (int i = 0; i < n; i++)
scanf("%lf %lf", &x[i], &y[i]);
// 求两点间最大距离
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
distance = sqrt(pow(x[i] - x[j], 2) + pow(y[i] - y[j], 2));
if (maxDistance < distance)
maxDistance = distance;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
distance = sqrt(pow(x[i] - x[j], 2) + pow(y[i] - y[j], 2));
if (maxDistance == distance)
cx = (x[i] + x[j]) / 2; // 最小覆盖圆圆心横坐标
cy = (y[i] + y[j]) / 2; // 最小覆盖圆圆心纵坐标
break;
// 最小覆盖圆半径
r = maxDistance / 2;
4
// 输出最小覆盖圆圆心坐标
printf("%.3f %.3f\\n", cx, cy);
// 输出最小覆盖圆半径
printf("%.3f\\n", r);
return 0;
(三)运行程序,查看结果
- 输入4,与四个点坐标
c案例:最小覆盖圆问题(代码片段)
文章目录一、提出任务-最小覆盖圆(一)描述(二)输入(三)输出(四)样例输入输出二、完成任务(一)编程思路(二)编写代码,实现功能(三)运行程序,查... 查看详情
java案例:最小覆盖圆问题
文章目录一、提出任务-最小覆盖圆(一)描述(二)输入(三)输出(四)样例输入输出二、完成任务(一)编程思路(二)编写代码,实现功能(三)运行程序,查看结果一、提出任务-最小覆盖圆(一)描述给出平面上N(N≤1... 查看详情
java案例:最小覆盖圆问题
文章目录一、提出任务-最小覆盖圆(一)描述(二)输入(三)输出(四)样例输入输出二、完成任务(一)编程思路(二)编写代码,实现功能(三)运行程序,查看结果一、提出任务-最小覆盖圆(一)描述给出平面上N(N≤1... 查看详情
java案例:最小覆盖圆问题
文章目录一、提出任务-最小覆盖圆(一)描述(二)输入(三)输出(四)样例输入输出二、完成任务(一)编程思路(二)编写代码,实现功能(三)运行程序,查看结果一、提出任务-最小覆盖圆(一)描述给出平面上N(N≤1... 查看详情
luogup1742最小圆覆盖(代码片段)
最小圆覆盖主要是我太菜了不会证明qwq,上面的博客讲的非常好。主要是存代码:#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>#include<cmath>usingnamespacestd;constintN=100009;constdoublee 查看详情
覆盖点问题总结(代码片段)
1.最小的包围圆,将所有的点包围起来。(hdu3932)最小覆盖圆算法地址:http://soft.cs.tsinghua.edu.cn/blog/?q=node/1066问题的背景提出:考察固定在工作平台上的一直机械手,要捡起散落在不同位置的多个零件,并送到别的地方。那么,... 查看详情
[matlab]10.最小覆盖圆(代码片段)
clearall;closeall;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;%求两点中点fori=3:nnewp=p(i,:);%从第三行开始储存新的点d=sqrt((cenp(1)-new 查看详情
bzoj1337最小圆覆盖(代码片段)
bzoj1337最小圆覆盖补充一个求三角形外心的向量法.用了点积的几何意义,很实用.出处.使用随机增量法求.首先随机打乱顺序,然后三重循环,选择当前在圆外的点更新圆,分别按照(1/2/3)个点确定圆的方式更新即可.由于随机一个点不在... 查看详情
p1742最小圆覆盖(代码片段)
(color#0066ff题目描述)给出N个点,让你画一个最小的包含所有点的圆。(color#0066ff输入格式)先给出点的个数N,2<=N<=100000,再给出坐标Xi,Yi.(-10000.0<=xi,yi<=10000.0)(color#0066ff输出格式)输出圆的半径,及圆心的坐标,保留10位小数(c... 查看详情
bzoj2823:[ahoi2012]信号塔&&1336:[balkan2002]alien最小圆覆盖&&1337:最小圆覆盖(代码片段)
首先我写了个凸包就溜了这是最小圆覆盖问题,今晚学了一下先随机化点,一个个加入假设当前圆心为o,半径为r,加入的点为i若i不在圆里面,令圆心为i,半径为0再重新从1~i-1不停找j不在圆里面,令圆心为ij中点,直径为ij距... 查看详情
[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'... 查看详情
最小圆覆盖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... 查看详情
做题poi2011r1-plot——最小圆覆盖&倍增(代码片段)
...将其划分成不超过(m)段连续的区间,使得所有每个区间的最小圆覆盖的半径的最大值最小。输出这个最小化的最大值和方案(圆心)。(n,mleq10^5)显然要二分答案。然后,一个区间就是越长越好。首先,考虑最小圆覆盖(O(n))的随机... 查看详情
模板最小圆覆盖——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... 查看详情
最小圆覆盖
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, 查看详情
最小圆覆盖
求一个半径最小的圆使其内部至少包含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 查看详情
网络流24题之1738:最小路径覆盖问题(代码片段)
网络流24题之1738:最小路径覆盖问题最小路径覆盖问题模板题,求一个图的最小路径覆盖,输出边数和,路径。不会输出路径的跑dinic然后把图输出来就懂了。#include<bits/stdc++.h>usingnamespacestd;intk;structDinicstaticconstintMAXN=30005+7;sta... 查看详情