3.7牛客2021年度训练联盟热身训练赛第一场A.Weird Flecks, But OK[最小覆盖圆]

本文主要是介绍3.7牛客2021年度训练联盟热身训练赛第一场A.Weird Flecks, But OK[最小覆盖圆],希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

时间限制:C/C++ 3秒,其他语言6秒
空间限制:C/C++ 262144K,其他语言524288K
Special Judge, 64bit IO Format: %lld

题目描述 

An artist who wanted to create an installation where his works appeared to be floating in midair has cast a large cube of clear acrylic to serve as a base. Unfortunately, during the casting, some small flecks of dirt got into the mix, and now appear as a cluster of pinpoint flaws in the otherwise clear cube. 

He wants to drill out the portion of the cube containing the flaws so that he can plug the removed volume with new, clear acrylic. He would prefer to do this in one drilling step. For stability’s sake, the drill must enter the cube only once, perpendicular to one of its faces. The cube’s faces are parallel to the coordinate axes. 

Given the (x,y,z) positions of the flaws, and treating the size of the flaws as negligible, what is the smallest diameter drill bit that can be used to remove the flaws in one operation?? 

输入描述:

 

The first line of input contains an integer N denoting the number of flaws. 3≤N≤5000

This is followed by N lines of input, each containing three real numbers in the range −1000.0…1000.0, denoting the (x,y,z) coordinates of a single flaw. Each number contains at most 6 digits following a decimal point. The decimal point may be omitted if all succeeding digits are zero.

输出描述:

 

Print the diameter of the smallest drill bit that would remove all the flaws.

The answer is considered correct if the absolute or relative error is less than 10-4

示例1

输入

复制

3
1.0 0.0 1.4
-1.0 0.0 -1.4
0.0 1.0 -0.2

输出

复制

2.0000000000

示例2

输入

复制

5
1.4 1.0 0.0
-0.4 -1.0 0.0
-0.1 -0.25 -0.5
-1.2 0.0 0.9
0.2 0.5 0.5

输出

复制

2.0000000000

示例3

输入

复制

8
435.249 -494.71 -539.356
455.823 -507.454 -539.257
423.394 -520.682 -538.858
446.507 -501.953 -539.37
434.266 -503.664 -560.631
445.059 -549.71 -537.501
449.65 -506.637 -513.778
456.05 -499.715 -561.329

输出

复制

49.9998293198

【最小覆盖圆】

知识点:https://blog.csdn.net/WhereIsHeroFrom/article/details/79531050

队友代码

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;const double eps = 1e-8;struct node{double x,y;
};
struct temp{double x,y,z;
};struct node p[5010],central;
struct temp t[5010];
double ansR=0x3f3f3f;
int n;double dist(struct node  a,struct node b){return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}//求外接圆圆心,根据三边相等
struct node circumcenter(struct node a,struct node b,struct node c)
{double a1=b.x-a.x, b1=b.y-a.y, c1=(a1*a1+b1*b1)/2;double a2=c.x-a.x, b2=c.y-a.y, c2=(a2*a2+b2*b2)/2;double d=a1*b2-a2*b1;struct node tmp;tmp.x = a.x + (c1*b2-c2*b1)/d ;tmp.y = a.y+(a1*c2-a2*c1)/d;return tmp;
}void min_cover_circle(){random_shuffle(p,p+n); central = p[0];int i,j,k;double R=0;for(i=1;i<n;i++){if(dist(central,p[i])+eps>R){central = p[i];R=0;for(j=0;j<i;j++){if(dist(central,p[j])+eps>R){central.x=(p[i].x+p[j].x)/2;central.y=(p[i].y+p[j].y)/2;R=dist(central,p[j]);for(k=0;k<j;k++){if(dist(central,p[k])+eps>R){central=circumcenter(p[i],p[j],p[k]);R=dist(central,p[k]);}}}}}}ansR=min(ansR,R);
}int main(){cin>>n;for(int i=0;i<n;i++){scanf("%lf%lf%lf",&t[i].x,&t[i].y,&t[i].z);}for(int i=0;i<n;i++) {p[i].x=t[i].x;	p[i].y=t[i].y;} min_cover_circle();for(int i=0;i<n;i++) {p[i].x=t[i].z;	p[i].y=t[i].y;} min_cover_circle();for(int i=0;i<n;i++) {p[i].x=t[i].z;	p[i].y=t[i].x;} min_cover_circle();
//	printf("(%.1lf,%.1lf).\n%.1lf\n",central.x,central.y,R);printf("%.10f\n",2*ansR); return 0;
}

自己代码

拿下面代码改的

https://blog.csdn.net/Vmurder/article/details/46605193?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522161510137816780255278832%2522%252C%2522scm%2522%253A%252220140713.130102334.pc%255Fall.%2522%257D&request_id=161510137816780255278832&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~first_rank_v2~hot_rank-6-46605193.pc_search_result_before_js&utm_term=2823信号塔

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<set>
#include<queue>
#include<stack>
#include<map>
#include<cmath>
using namespace std;
typedef long long ll;
#define Inf 0xfffffff
#define N 501000
#define eps 1e-7
using namespace std;double min_r=Inf;struct Point
{double x,y;Point(double _x=0,double _y=0):x(_x),y(_y){x=_x;y=_y;}void read(){scanf("%lf%lf",&x,&y);}bool operator < (const Point &A)const{return fabs(x-A.x)<eps?y<A.y:x<A.x;}double operator - (const Point &A)const{return sqrt((x-A.x)*(x-A.x)+(y-A.y)*(y-A.y));}void print(){printf("%.2lf %.2lf ",x,y);}
}p1[N],p2[N],p3[N];struct Circle
{Point c; // centerdouble r;Circle(Point _c=Point(0,0),double _r=0):c(_c),r(_r){}bool operator ^ (const Point &A)const{return A-c>r+eps;} // 包含void print(){//c.print();if(r<min_r)min_r=r;}
};inline double xmul(const Point &A,const Point &B,const Point &C)
{return (C.y-A.y)*(B.x-A.x)-(B.y-A.y)*(C.x-A.x);}struct Get_Convex_Hull
{//求凸包int stk1[N],top1,stk2[N],top2;Point tp[N];void work(Point *p,int &n){int i;sort(p+1,p+n+1);stk1[top1=1]=1;for(i=2;i<=n;i++){while(top1>1&&xmul(p[stk1[top1-1]],p[stk1[top1]],p[i])>-eps)top1--;stk1[++top1]=i;}stk2[top2=1]=n;for(i=n-1;i;i--){while(top2>1&&xmul(p[stk2[top2-1]],p[stk2[top2]],p[i])>-eps)top2--;stk2[++top2]=i;}n=0;for(i=1;i<top1;i++)tp[++n]=p[stk1[i]];for(i=1;i<top2;i++)tp[++n]=p[stk2[i]];for(i=1;i<=n;i++)p[i]=tp[i];}
}gch;struct Get_Min_Circle_Cover1
{Point circumcenter(const Point &a,const Point &b,const Point &c){//返回三角形的外心 我并不知道这是什么鬼。。好强的样子。Point ret;double a1=b.x-a.x,b1=b.y-a.y,c1=(a1*a1+b1*b1)/2;double a2=c.x-a.x,b2=c.y-a.y,c2=(a2*a2+b2*b2)/2;double d=a1*b2-a2*b1;ret.x=a.x+(c1*b2-c2*b1)/d;ret.y=a.y+(a1*c2-a2*c1)/d;return ret;}Circle work(int n){random_shuffle(p1+1,p1+n+1);Circle C=Circle(p1[1],0);int i,j,k;for(i=2;i<=n;i++)if(C^p1[i]){C=Circle(p1[i],0);for(j=1;j<i;j++)if(C^p1[j]){C.c=Point((p1[i].x+p1[j].x)/2,(p1[i].y+p1[j].y)/2);C.r=p1[j]-C.c;for(k=1;k<j;k++)if(C^p1[k])//求外接圆圆心,要求三点不能共线C.c=circumcenter(p1[i],p1[j],p1[k]),C.r=C.c-p1[i];}}return C;}
}gmcc1;struct Get_Min_Circle_Cover2
{Point circumcenter(const Point &a,const Point &b,const Point &c){//返回三角形的外心 我并不知道这是什么鬼。。好强的样子。Point ret;double a1=b.x-a.x,b1=b.y-a.y,c1=(a1*a1+b1*b1)/2;double a2=c.x-a.x,b2=c.y-a.y,c2=(a2*a2+b2*b2)/2;double d=a1*b2-a2*b1;ret.x=a.x+(c1*b2-c2*b1)/d;ret.y=a.y+(a1*c2-a2*c1)/d;return ret;}Circle work(int n){random_shuffle(p2+1,p2+n+1);Circle C=Circle(p2[1],0);int i,j,k;for(i=2;i<=n;i++)if(C^p2[i]){C=Circle(p2[i],0);for(j=1;j<i;j++)if(C^p2[j]){C.c=Point((p2[i].x+p2[j].x)/2,(p2[i].y+p2[j].y)/2);C.r=p2[j]-C.c;for(k=1;k<j;k++)if(C^p2[k])//求外接圆圆心,要求三点不能共线C.c=circumcenter(p2[i],p2[j],p2[k]),C.r=C.c-p2[i];}}return C;}
}gmcc2;struct Get_Min_Circle_Cover3
{Point circumcenter(const Point &a,const Point &b,const Point &c){//返回三角形的外心 我并不知道这是什么鬼。。好强的样子。Point ret;double a1=b.x-a.x,b1=b.y-a.y,c1=(a1*a1+b1*b1)/2;double a2=c.x-a.x,b2=c.y-a.y,c2=(a2*a2+b2*b2)/2;double d=a1*b2-a2*b1;ret.x=a.x+(c1*b2-c2*b1)/d;ret.y=a.y+(a1*c2-a2*c1)/d;return ret;}Circle work(int n){random_shuffle(p3+1,p3+n+1);Circle C=Circle(p3[1],0);int i,j,k;for(i=2;i<=n;i++)if(C^p3[i]){C=Circle(p3[i],0);for(j=1;j<i;j++)if(C^p3[j]){C.c=Point((p3[i].x+p3[j].x)/2,(p3[i].y+p3[j].y)/2);C.r=p3[j]-C.c;for(k=1;k<j;k++)if(C^p3[k])//求外接圆圆心,要求三点不能共线C.c=circumcenter(p3[i],p3[j],p3[k]),C.r=C.c-p3[i];}}return C;}
}gmcc3;int main()
{
//  freopen("test.in","r",stdin);int n;scanf("%d",&n);for(int i=1;i<=n;i++){double x,y,z;cin>>x>>y>>z;p1[i].x=x;p1[i].y=y;p2[i].x=y;p2[i].y=z;p3[i].x=x;p3[i].y=z;}
//  gch.work(p,n);Circle ret1=gmcc1.work(n);ret1.print();Circle ret2=gmcc2.work(n);ret2.print();Circle ret3=gmcc3.work(n);ret3.print();printf("%.10lf",min_r*2);return 0;
}

 

这篇关于3.7牛客2021年度训练联盟热身训练赛第一场A.Weird Flecks, But OK[最小覆盖圆]的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/209041

相关文章

poj 1258 Agri-Net(最小生成树模板代码)

感觉用这题来当模板更适合。 题意就是给你邻接矩阵求最小生成树啦。~ prim代码:效率很高。172k...0ms。 #include<stdio.h>#include<algorithm>using namespace std;const int MaxN = 101;const int INF = 0x3f3f3f3f;int g[MaxN][MaxN];int n

poj 1287 Networking(prim or kruscal最小生成树)

题意给你点与点间距离,求最小生成树。 注意点是,两点之间可能有不同的路,输入的时候选择最小的,和之前有道最短路WA的题目类似。 prim代码: #include<stdio.h>const int MaxN = 51;const int INF = 0x3f3f3f3f;int g[MaxN][MaxN];int P;int prim(){bool vis[MaxN];

poj 2349 Arctic Network uva 10369(prim or kruscal最小生成树)

题目很麻烦,因为不熟悉最小生成树的算法调试了好久。 感觉网上的题目解释都没说得很清楚,不适合新手。自己写一个。 题意:给你点的坐标,然后两点间可以有两种方式来通信:第一种是卫星通信,第二种是无线电通信。 卫星通信:任何两个有卫星频道的点间都可以直接建立连接,与点间的距离无关; 无线电通信:两个点之间的距离不能超过D,无线电收发器的功率越大,D越大,越昂贵。 计算无线电收发器D

poj 1734 (floyd求最小环并打印路径)

题意: 求图中的一个最小环,并打印路径。 解析: ans 保存最小环长度。 一直wa,最后终于找到原因,inf开太大爆掉了。。。 虽然0x3f3f3f3f用memset好用,但是还是有局限性。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#incl

hdu 1102 uva 10397(最小生成树prim)

hdu 1102: 题意: 给一个邻接矩阵,给一些村庄间已经修的路,问最小生成树。 解析: 把已经修的路的权值改为0,套个prim()。 注意prim 最外层循坏为n-1。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstri

poj 2175 最小费用最大流TLE

题意: 一条街上有n个大楼,坐标为xi,yi,bi个人在里面工作。 然后防空洞的坐标为pj,qj,可以容纳cj个人。 从大楼i中的人到防空洞j去避难所需的时间为 abs(xi - pi) + (yi - qi) + 1。 现在设计了一个避难计划,指定从大楼i到防空洞j避难的人数 eij。 判断如果按照原计划进行,所有人避难所用的时间总和是不是最小的。 若是,输出“OPETIMAL",若

poj 2135 有流量限制的最小费用最大流

题意: 农场里有n块地,其中约翰的家在1号地,二n号地有个很大的仓库。 农场有M条道路(双向),道路i连接着ai号地和bi号地,长度为ci。 约翰希望按照从家里出发,经过若干块地后到达仓库,然后再返回家中的顺序带朋友参观。 如果要求往返不能经过同一条路两次,求参观路线总长度的最小值。 解析: 如果只考虑去或者回的情况,问题只不过是无向图中两点之间的最短路问题。 但是现在要去要回

poj 3422 有流量限制的最小费用流 反用求最大 + 拆点

题意: 给一个n*n(50 * 50) 的数字迷宫,从左上点开始走,走到右下点。 每次只能往右移一格,或者往下移一格。 每个格子,第一次到达时可以获得格子对应的数字作为奖励,再次到达则没有奖励。 问走k次这个迷宫,最大能获得多少奖励。 解析: 拆点,拿样例来说明: 3 2 1 2 3 0 2 1 1 4 2 3*3的数字迷宫,走两次最大能获得多少奖励。 将每个点拆成两个

poj 2195 bfs+有流量限制的最小费用流

题意: 给一张n * m(100 * 100)的图,图中” . " 代表空地, “ M ” 代表人, “ H ” 代表家。 现在,要你安排每个人从他所在的地方移动到家里,每移动一格的消耗是1,求最小的消耗。 人可以移动到家的那一格但是不进去。 解析: 先用bfs搞出每个M与每个H的距离。 然后就是网络流的建图过程了,先抽象出源点s和汇点t。 令源点与每个人相连,容量为1,费用为

poj 3068 有流量限制的最小费用网络流

题意: m条有向边连接了n个仓库,每条边都有一定费用。 将两种危险品从0运到n-1,除了起点和终点外,危险品不能放在一起,也不能走相同的路径。 求最小的费用是多少。 解析: 抽象出一个源点s一个汇点t,源点与0相连,费用为0,容量为2。 汇点与n - 1相连,费用为0,容量为2。 每条边之间也相连,费用为每条边的费用,容量为1。 建图完毕之后,求一条流量为2的最小费用流就行了