Gym - 101981D The 2018 ICPC Asia Nanjing Regional Contest D.Country Meow 最小球覆盖
2024-10-01 02:02:07
题意:给你100个三维空间里的点,让你求一个点,使得他到所有点距离最大的值最小,也就是让你找一个最小的球覆盖掉这n个点
题解:红书模板题,这题也因为数据小,精度也不高,所以也可以用随机算法,模拟退火之类的
#include<bits/stdc++.h>
using namespace std;
int npoint,nouter;
struct Tpoint
{
double x,y,z;
};
Tpoint pt[],outer[],res;
#define eps 1e-9
double radius,tmp;
inline double dist(Tpoint p1,Tpoint p2)
{
double dx=p1.x-p2.x,dy=p1.y-p2.y,dz=p1.z-p2.z;
return (dx*dx+dy*dy+dz*dz);
}
inline double dot(Tpoint p1,Tpoint p2)
{
return p1.x*p2.x+p1.y*p2.y+p1.z*p2.z;
}
void ball()
{
Tpoint q[];
double m[][],sol[],L[],det;
int i,j;
res.x=res.y=res.z=radius=;
switch (nouter)
{
case :res=outer[];break;
case :
res.x=(outer[].x+outer[].x)/;
res.y=(outer[].y+outer[].y)/;
res.z=(outer[].z+outer[].z)/;
radius=dist(res,outer[]);
break;
case :
for (int i=;i<;i++)
{
q[i].x=outer[i+].x-outer[].x;
q[i].y=outer[i+].y-outer[].y;
q[i].z=outer[i+].z-outer[].z;
}
for (int i=;i<;i++)
for (int j=;j<;j++)
m[i][j]=dot(q[i],q[j])*;
for (int i=;i<;i++) sol[i]=dot(q[i],q[i]);
if (fabs(det=m[][]*m[][]-m[][]*m[][])<eps) return;
L[]=(sol[] * m[][] - sol[] * m[][])/det;
L[]=(sol[] * m[][] - sol[] * m[][])/det;
res.x=outer[].x+q[].x*L[]+q[].x*L[];
res.y=outer[].y+q[].y*L[]+q[].y*L[];
res.z=outer[].z+q[].z*L[]+q[].z*L[];
radius=dist(res,outer[]);
break;
case :
for (int i=;i<;i++)
{
q[i].x=outer[i+].x-outer[].x;
q[i].y=outer[i+].y-outer[].y;
q[i].z=outer[i+].z-outer[].z;
sol[i]=dot(q[i],q[i]);
}
for (int i=;i<;i++)
for (int j=;j<;j++) m[i][j]=dot(q[i],q[j])*;
det=m[][]*m[][]*m[][]
+m[][]*m[][]*m[][]
+m[][]*m[][]*m[][]
-m[][]*m[][]*m[][]
-m[][]*m[][]*m[][]
-m[][]*m[][]*m[][];
if (fabs(det)<eps) return ;
for (int j=;j<;j++)
{
for (int i=;i<;i++)
m[i][j]=sol[i];
L[j]=( m[][]*m[][]*m[][]
+m[][]*m[][]*m[][]
+m[][]*m[][]*m[][]
-m[][]*m[][]*m[][]
-m[][]*m[][]*m[][]
-m[][]*m[][]*m[][]
)/det;
for (int i=;i<;i++)
m[i][j]=dot(q[i],q[j])*;
}
res=outer[];
for (int i=;i<;i++)
{
res.x+=q[i].x*L[i];
res.y+=q[i].y*L[i];
res.z+=q[i].z*L[i];
}
radius=dist(res,outer[]);
}
}
void minball(int n)
{
ball();
if (nouter<)
{
for (int i=;i<n;i++)
if (dist(res,pt[i])-radius>eps)
{
outer[nouter]=pt[i];
++nouter;
minball(i);
--nouter;
if (i>)
{
Tpoint Tt=pt[i];
memmove(&pt[],&pt[],sizeof(Tpoint)*i);
pt[]=Tt;
}
}
}
}
int main()
{
radius=-;
scanf("%d",&npoint);
for (int i=;i<npoint;i++)
{
scanf("%lf%lf%lf",&pt[i].x,&pt[i].y,&pt[i].z);
}
for (int i=;i<npoint;i++)
if (dist(res,pt[i])-radius>eps)
{
nouter=;
outer[]=pt[i];
minball(i);
}
printf("%.10lf\n",sqrt(radius));
}
最新文章
- 【初探Spring】------Spring IOC（二）：初始化过程---简介
- 数据结构与算法分析 java语音描述（引论）
- Mac系统下使用VirtualBox虚拟机安装win7－－第三步 在虚拟机上安装 Windows 7
- Datagard產生gap
- 记录linux /bin被误删除的解决过程
- JavaWeb基础: XML基础知识
- 字典树(Trie树)的实现及应用
- Combine String---hdu5727 &&& Zipper（LCS变形）
- 在Ubuntu上为Android增加硬件抽象层（HAL）模块访问Linux内核驱动程序（老罗学习笔记3）
- [Redux] Passing the Store Down Implicitly via Context
- C# 后台调用script使用类
- [Q]升级/重新获取授权步骤
- Java线程-异常处理
- poj-3177（无向图缩点）
- 两种方法上传本地文件到github(转)
- 浅谈C++ STL
- 小甲鱼Python第十七讲课后习题
- apt-get update 更新 ubuntu时出现Hash sum mismatch的原因及解决方法
- C#的值传递与引用传递
- nginx 番外----添加第三方模块