首页 > 代码库 > BZOJ 2823 AHOI 2012 信号塔 凸包+最小圆覆盖
BZOJ 2823 AHOI 2012 信号塔 凸包+最小圆覆盖
题目大意:给出平面上n个点,求最小圆覆盖。
思路:圆覆盖问题只与所有点中凸包上的点有关,因此先求一下凸包,然后数据范围骤减。大概是只剩下logn左右个点。这样就可以随便浪了。
先找所有三个点组成的圆,然后找两个点为直径所组成的圆。
还有就是三角形的外心公式,简直不是人推的,然后我就机制的百度了,结果如下:
不要模拟退火。。。
样例很坑,当你算出2.49 2.86的时候,不要认为你被卡精了,其实是你写挂了。。。
CODE:
#include <cmath> #include <cstdio> #include <iomanip> #include <cstring> #include <iostream> #include <algorithm> #define MAX 1000010 #define INF 1e15 using namespace std; #define sqr(a) ((a) * (a)) struct Point{ double x,y,alpha; Point(double _,double __):x(_),y(__) {} Point() {} bool operator <(const Point &a)const { return alpha < a.alpha; } Point operator -(const Point &a)const { return Point(x - a.x,y - a.y); } void Read() { scanf("%lf%lf",&x,&y); } void Calc(const Point &p) { alpha = atan2(y - p.y,x - p.x); } }point[MAX]; int cnt; double min_x = INF,min_y = INF; Point stack[MAX]; int top; double Cross(const Point &p,const Point &q) { return p.x * q.y - p.y * q.x; } double Calc(const Point &a,const Point &b) { return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y)); } double CalcX(const Point &p1,const Point &p2,const Point &p3) { double up = sqr(p1.x) * (p2.y - p3.y) + sqr(p2.x) * (p3.y - p1.y) + sqr(p3.x) * (p1.y - p2.y); up -= (p1.y - p2.y) * (p2.y - p3.y) * (p3.y - p1.y); double down = p1.x * (p2.y - p3.y) + p2.x * (p3.y - p1.y) + p3.x * (p1.y - p2.y); return up / (2 * down); } double CalcY(const Point &p1,const Point &p2,const Point &p3) { double up = -(sqr(p1.y) * (p2.x - p3.x) + sqr(p2.y) * (p3.x - p1.x) + sqr(p3.y) * (p1.x - p2.x)); up += (p1.x - p2.x) * (p2.x - p3.x) * (p3.x - p1.x); double down = p1.x * (p2.y - p3.y) + p2.x * (p3.y - p1.y) + p3.x * (p1.y - p2.y); return up / (2 * down); } inline double Judge(double x,double y) { double re = .0; for(int i = 0; i <= top; ++i) re = max(re,Calc(Point(x,y),stack[i])); return re; } int main() { cin >> cnt; for(int i = 1; i <= cnt; ++i) point[i].Read(); int p; for(int i = 1; i <= cnt; ++i) if(point[i].y < min_y) { min_y = point[i].y; min_x = point[i].x; p = i; } else if(point[i].y == min_y && point[i].x < min_x) { min_x = point[i].x; p = i; } for(int i = 1; i <= cnt; ++i) if(i != p) point[i].Calc(point[p]); sort(point + 1,point + cnt + 1); stack[top] = point[1]; stack[++top] = point[2]; stack[++top] = point[3]; for(int i = 4; i <= cnt; ++i) { while(top >= 2 && Cross(stack[top] - stack[top - 1],point[i] - stack[top - 1]) <= 0) --top; stack[++top] = point[i]; } double ans = INF; double X,Y,x,y,r; for(int i = 0; i <= top; ++i) for(int j = i + 1; j <= top; ++j) for(int k = j + 1; k <= top; ++k) { x = CalcX(stack[i],stack[j],stack[k]); y = CalcY(stack[i],stack[j],stack[k]); r = Judge(x,y); if(r < ans) { ans = r; X = x,Y = y; } } for(int i = 0; i <= top; ++i) for(int j = 0; j <= top; ++j) { r = Judge((stack[i].x + stack[j].x) / 2,(stack[i].y + stack[j].y) / 2); if(r < ans) { ans = r; X = (stack[i].x + stack[j].x) / 2; Y = (stack[i].y + stack[j].y) / 2; } } printf("%.2lf %.2lf %.2lf\n",X,Y,ans); return 0; }
BZOJ 2823 AHOI 2012 信号塔 凸包+最小圆覆盖
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。