首页 > 代码库 > ZOJ 1450 Minimal Circle 最小圆覆盖
ZOJ 1450 Minimal Circle 最小圆覆盖
套了个模板直接上,貌似没有随机化序列 QAQ
//#pragma comment(linker, "/STACK:16777216") //for c++ Compiler#include <stdio.h>#include <iostream>#include <cstring>#include <cmath>#include <stack>#include <queue>#include <vector>#include <algorithm>#define ll long long#define Max(a,b) (((a) > (b)) ? (a) : (b))#define Min(a,b) (((a) < (b)) ? (a) : (b))#define Abs(x) (((x) > 0) ? (x) : (-(x)))using namespace std;const int INF = 0x3f3f3f3f;const int MAXN = 220;const double eps = 1e-9;struct POINT{ double x; double y; POINT() : x(0), y(0) {}; POINT(double _x_, double _y_) : x(_x_), y(_y_) {};};struct CIRCLE{ POINT p; double r; CIRCLE() {}; CIRCLE(POINT _p_, double _r_) : p(_p_), r(_r_) {};};double dist(POINT a,POINT b){ return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}CIRCLE calc(POINT p1,POINT p2,POINT p3){//三点的外接圆圆心的函数: CIRCLE temp; double a,b,c,d,e,f; a = p2.x - p1.x; b = p2.y - p1.y; c = (p2.x * p2.x + p2.y * p2.y - p1.x * p1.x - p1.y * p1.y) / 2; d = p3.x - p1.x; e = p3.y - p1.y; f = (p3.x * p3.x + p3.y * p3.y - p1.x * p1.x - p1.y * p1.y) / 2; temp.p.y = (c * d - f * a) / (b * d - e * a); temp.p.x = (c * e - f * b) / (a * e - b * d); return temp;}CIRCLE minC(POINT *p,int n){ CIRCLE O; int i,j,k; O.p = p[0]; O.r = 0; for(i= 1; i < n ; i++){ if(dist(O.p,p[i]) <= O.r + eps) continue; O.p = p[i];O.r = 0; for(j = 0; j < i; j++){ if(dist(O.p,p[j]) <= O.r + eps) continue; O.p.x = (p[i].x + p[j].x) / 2; O.p.y = (p[i].y + p[j].y) / 2; O.r = dist(O.p,p[j]); for(k = 0; k < j; k++){ if(dist(O.p,p[k]) <= O.r + eps) continue; O = calc(p[i],p[j],p[k]); O.r = dist(O.p,p[k]); } } } return O;}int main(){ int i, j, n; POINT p[200]; while(EOF != scanf("%d",&n)){ if(n == 0) break; for(i = 0; i < n; ++i) scanf("%lf%lf",&p[i].x,&p[i].y); CIRCLE c = minC(p, n); printf("%.2f %.2f %.2f\n",c.p.x,c.p.y,c.r); } return 0;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。