程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> BZOJ 2823 AHOI 2012 信號塔 凸包+最小圓覆蓋

BZOJ 2823 AHOI 2012 信號塔 凸包+最小圓覆蓋

編輯:關於C++

題目大意:給出平面上n個點,求最小圓覆蓋。


思路:圓覆蓋問題只與所有點中凸包上的點有關,因此先求一下凸包,然後數據范圍驟減。大概是只剩下logn左右個點。這樣就可以隨便浪了。

先找所有三個點組成的圓,然後找兩個點為直徑所組成的圓。

還有就是三角形的外心公式,簡直不是人推的,然後我就機制的百度了,結果如下:

\

不要模擬退火。。。<喎?/kf/ware/vc/" target="_blank" class="keylink">vcD4KPHA+0fnA/brcv9OjrLWxxOPL47P2Mi40OSAyLjg2tcTKsbryo6yyu9KqyM/OqsTjsbu/qL6rwcujrMbkyrXKx8Tj0LS50sHLoaOho6GjPC9wPgo8cD48YnI+CjwvcD4KPHA+Q09ERaO6PGJyPgo8YnI+CjxwcmUgY2xhc3M9"brush:java;">#include #include #include #include #include #include #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; }

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved