BZOJ 2823 AHOI2012 信號塔 計算幾何
題目大意：給定n個點(n<=50W)，求最小圓覆蓋
逗我？n<=50W？最小圓覆蓋？O(n^3)？
其實數據是隨機生成的 經過驗證 隨機生成50w的點集 平均在凸包上的點在50~60個左右
於是求凸包之後就可以隨便亂搞了- - 不會寫O(n^3)的最小圓覆蓋 寫了O(n^4)的照過
注意最小圓覆蓋時要討論有兩點在圓上和有三點在圓上兩種情況
--------------------以上是題解-----------以下是粗口---------------------
出題人我*你*！！數據隨機生成的就不能【哔】一聲麼！！本大爺刷這題卡了5個小時啊啊啊！
剛開始覺得做不了寫了模擬退火有木有啊！！WA成狗啊有木有！！！
還有TM那坑B的樣例是怎麼個鬼！
void Sample_Explanation(bool f**k)
{
最後求得的圓是由第一個點和第三個點所構成的線段作為直徑的圓
其中第五個點雖然怎麼看怎麼在圓上 但是這個點實際上是在圓內
如果求得答案為(2.49,2.86)，並不是被卡精度了，而是找到了由第1、3、5三個點構成的圓
顯然這個圓並不是最優解
參考圖片：
}
#include
#include
#include
#include
#include
#include
#define M 500500
#define INF 1e20
#define EPS 1e-7
using namespace std;
struct point{
double x,y;
point(){}
point(double _,double __):x(_),y(__) {}
void Read()
{
x=rand();y=rand();
}
bool operator < (const point &p) const
{
if(fabs(x-p.x)>1e-7)
return x < p.x;
return y < p.y;
}
}points[M],ans;
int n;
double ans_distance=INF;
point *stack[M];int top;
point *on_the_hull[M];int cnt;
double Rand()
{
return rand()%10000/10000.0;
}
double Distance(const point &p1,const point &p2)
{
double dx=p1.x-p2.x;
double dy=p1.y-p2.y;
return sqrt(dx*dx+dy*dy);
}
double Get_Slope(const point &p1,const point &p2)
{
if(fabs(p1.x-p2.x)=2&&Get_Slope(*stack[top-1],*stack[top])=2&&Get_Slope(*stack[top-1],*stack[top])>Get_Slope(*stack[top],points[i])-EPS)
stack[top--]=0x0;
stack[++top]=&points[i];
}
for(top--;top>1;top--)
on_the_hull[++cnt]=stack[top];
}
point Get_Centre(const point &a,const point &b,const point &c)
{
long double a1=a.x-b.x,b1=a.y-b.y,c1=0.5*( (a.x*a.x-b.x*b.x) + (a.y*a.y-b.y*b.y) );
long double a2=a.x-c.x,b2=a.y-c.y,c2=0.5*( (a.x*a.x-c.x*c.x) + (a.y*a.y-c.y*c.y) );
return point( (c2*b1-c1*b2)/(a2*b1-a1*b2) , (a2*c1-a1*c2)/(a2*b1-a1*b2) );
}
void Judge(const point &p)
{
int i;
double max_distance=0;
for(i=1;i<=cnt;i++)
{
max_distance=max(max_distance,Distance(p,*on_the_hull[i]) );
if(max_distance>ans_distance)
return ;
}
ans=p;ans_distance=max_distance;
}
int main()
{
srand((unsigned)time(0x0));
int i,j,k;
cin>>n;
for(int T=1000;T;T--)
{
top=0;cnt=0;
for(i=1;i<=n;i++)
points[i].Read();
Get_Convex_Hull();
cout<
·
