频道栏目
首页 > 考试 > 其他 > 正文

BZOJ 1336&1337最小圆覆盖

2017-01-07 09:25:00      个评论    来源:SiriusRen的博客  
收藏   我要投稿

(照着算法步骤写……)
已知三点共圆 求圆心的时候 就设一下圆心坐标(x,y) 解个方程就好了

//By SiriusRen
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
int n;double R,tempx,tempy,tempz,tmpx,tmpy,tmpz;
struct Point{double x,y;}point[100050],Ans;
double Sqr(double x){return x*x;}
double dis(Point a,Point b){return sqrt(Sqr(a.x-b.x)+Sqr(a.y-b.y));}
bool in_circle(Point x){return dis(Ans,x)<=R;}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%lf%lf",&point[i].x,&point[i].y);
    random_shuffle(point+1,point+n);
    for(int i=1;i<=n;i++)if(!in_circle(point[i])){
        Ans.x=point[i].x,Ans.y=point[i].y,R=0;
        for(int j=1;j<i;j++)if(!in_circle(point[j])){ ans.x="(point[i].x+point[j].x)/2;" ans.y="(point[i].y+point[j].y)/2;" r="dis(Ans,point[j]);" int="" k="1;k<j;k++)if(!in_circle(point[k])){" tempz="point[j].x-point[i].x;" tempx="2*(point[i].y-point[j].y)/tempz;" tempy="(Sqr(point[j].x)+Sqr(point[j].y)-Sqr(point[i].x)-Sqr(point[i].y))/tempz;" tmpz="point[k].x-point[j].x;" tmpx="2*(point[j].y-point[k].y)/tmpz;" tmpy="(Sqr(point[k].x)+Sqr(point[k].y)-Sqr(point[j].x)-Sqr(point[j].y))/tmpz;" f="" pre="">

这里写图片描述

上一篇:uoj #86 mx的组合数 FFT 原根
下一篇:【LeetCode】 442. Find All Duplicates in an Array
相关文章
图文推荐

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训

版权所有: 红黑联盟--致力于做实用的IT技术学习网站