Gym 101606B Breaking Biscuits [ 计算几何 ]

题意：给定一个规则多边形，求一个最小的圆，能包含整个多边形，求这个圆的直径。。。

思路：就是直接枚举每一条直线，求这条直线的两边的点到直线的最大距离即可。。。

代码：

#include<bits/stdc++.h>
#include<algorithm>
using namespace std;
const int N=111;
struct P{
int x,y;
P(){}
P(int _x,int _y){x=_x,y=_y;}
P operator-(P b){return P(x-b.x,y-b.y);} //向量x -> b
double len(){return hypot(x,y);}
//sqrt(x*x + y*y);
} a[N];
int n,i,j,k;
double ans=1e100;
double cross(P a,P b){return a.x*b.y-a.y*b.x;}
//向量点积，求一点到直线的距离；
double dist(P p,P a,P b){
return cross(p-a,b-a)/(b-a).len();
//tan求点到直线的距离。。。
}
int main(){
//freopen("in.txt", "r", stdin);
scanf("%d", &n);
for(i = 1;i <= n; i++) scanf("%d%d",&a[i].x,&a[i].y);
for(i = 1; i <= n; i++)
for(j = 1; j < i; j++){
double l=1e100,r=-1e100;
for(k = 1; k <= n; k++){
l=min(l,dist(a[k],a[i],a[j])); //线段ij一侧的最大距离；
r=max(r,dist(a[k],a[i],a[j])); //线段ij另一侧的最大距离；
}
r -= l;
ans = min(ans, r);
}
printf("%.10fn",ans);
}

最后

以上就是害怕猫咪为你收集整理的Gym 101606B Breaking Biscuits [ 计算几何 ]的全部内容，希望文章能够帮你解决Gym 101606B Breaking Biscuits [ 计算几何 ]所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。