最小圆覆盖裸题

我求外接圆的方法比较奇怪…不过还是过掉了

#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<algorithm>
using namespace std;
const int N=505;
struct Point
{
double x,y;
int rnd;
Point(double x=0,double y=0):x(x),y(y){}
}p[N];
struct Line
{
double k,b;
};
inline Line calcLine(double k,Point a)
{
Line res;res.k=k;
res.b=a.y-k*a.x;
return res;
}
inline Point operator +(Point a,Point b)
{
return Point(a.x+b.x,a.y+b.y);
}
inline Point operator -(Point a,Point b)
{
return Point(a.x-b.x,a.y-b.y);
}
inline Point operator /(Point a,double d)
{
return Point(a.x/d,a.y/d);
}
inline Point lineIntersection(Line l1,Line l2)
{
Point res;
res.x=(l2.b-l1.b)/(l1.k-l2.k);
res.y=l1.k*res.x+l1.b;
return res;
}
/*
inline Point getCircle(Point a,Point b,Point c)
{
double k1=-(b.x-a.x)/(b.y-a.y);
double k2=-(c.x-a.x)/(c.y-a.y);
Point p1=(a+b)/2,p2=(a+c)/2;
Line l1=calcLine(k1,p1),l2=calcLine(k2,p2);
return lineIntersection(l1,l2);
}
*/
inline Point getCircle(Point a,Point b,Point c)
{
Point center;
double a1 = b.x - a.x;
double b1 = b.y - a.y;
double c1 = (a1 * a1 + b1 * b1) / 2.0;
double a2 = c.x - a.x;
double b2 = c.y - a.y;
double c2 = (a2 * a2 + b2 * b2) / 2.0;
double d = a1 * b2 - a2 * b1;
center.x = a.x + (c1 * b2 - c2 * b1) / d;
center.y = a.y + (a1 * c2 - a2 * c1) / d;
return center;
}
inline bool cmp(Point a,Point b)
{
return a.rnd<b.rnd;
}
inline double sqr2(double x){return x*x;}
inline double dot(Point a,Point b)
{
return a.x*b.x+a.y*b.y;
}
inline double dist(Point a,Point b)
{
return sqrt(dot(a-b,a-b));
}
inline int dblcmp(double x)
{
if(fabs(x)<1e-6)return 0;
return (x>0?1:-1);
}
int n;
inline Point minCircle(double &r)
{
sort(p+1,p+n+1,cmp);
Point o=p[1];r=0;
for(register int i=2;i<=n;i++)if(r<dist(o,p[i]))
{
o=p[i];r=0;
for(register int j=1;j<i;j++)if(r<dist(o,p[j]))
{
o=(p[i]+p[j])/2;
r=dist(o,p[j]);
for(register int k=1;k<j;k++)if(r<dist(o,p[k]))
{
o=getCircle(p[i],p[j],p[k]);
r=dist(o,p[i]);
}
}
}
return o;
}
int main()
{
while(scanf("%d",&n)==1&&n)
{
for(register int i=1;i<=n;i++)scanf("%lf%lf",&p[i].x,&p[i].y),p[i].rnd=rand();
double r;Point res=minCircle(r);printf("%.2lf %.2lf %.2lf\n",res.x,res.y,r);
}
return 0;
}

最新文章

  1. Leetcode 刷题计划
  2. Spring系列:学习Spring的资源和讨论
  3. coffeeScript中类的多态[学习篇]
  4. 介绍开源的.net通信框架NetworkComms框架 源码分析(二十 )ConnectionCreate
  5. C#回顾 &ndash; 4.IEnumerable 集合
  6. (转)POJ题目分类
  7. 整理的java的日期DateUtil
  8. 豆瓣移动端风格的css命名方法与学习
  9. 多线程之线程池Executor应用
  10. C++标准模板库(STL)之Vector
  11. 项目启动失败,异常代码(StandardEngine[Catalina].StandardHost[localhost].StandardContext[/credit]]) ,dataSource 也报错
  12. [20190321]smem的显示缺陷.txt
  13. mysql 行转列 列转行
  14. spring AOP自定义注解方式实现日志管理
  15. jenkins 结合 jmeter 的报告篇
  16. Html5与Css3知识点拾遗(三)
  17. Flask的请求对象--request
  18. Java 线程类的一些常用方法
  19. spring@Transactional的一点理解
  20. etl数据库查询

热门文章

  1. 如何调整MathType公式的字体大小
  2. 常见的名片尺寸如何在CorelDRAW预设
  3. react-hash-calendar,移动端日期时间选择插件
  4. Linux中的基本命令无法使用,报Command not found的错误的解决方法
  5. 【不尽如人意的redisTemplete封装】
  6. CentOS6.5上增加中文字体库,确保前端WEB可以正常显示
  7. 14_TTS
  8. cookie 与session
  9. Spring Cloud Alibaba 初体验(三) Nacos 与 Dubbo 集成
  10. Java中正则表达式的使用(常用的方法)