BZOJ 2280 Poi2011 Plot 二分答案+隨機增量法

BZOJ 2280 Poi2011 Plot 二分答案+隨機增量法

題目大意：給定n個點，要求分成m段，使每段最小覆蓋圓半徑的最大值最小

二分答案，然後驗證的時候把點一個個塞進最小覆蓋圓中，若半徑超了就分成一塊……

等等你在跟我說不隨機化的隨機增量法？

好吧

那麼對於一個點pos，我們要計算最大的bound滿足[pos,bound]區間內的最小覆蓋圓半徑不超過二分的值

直接上二分是不可取的，因為我們要求m次，如果每次都驗證一遍[1,n/2]直接就炸了

我們可以這麼搞

首先判斷[pos,pos+1-1]是否滿足要求

然後判斷[pos,pos+2-1]是否滿足要求

然後判斷[pos,pos+4-1]是否滿足要求

然後判斷[pos,pos+8-1]是否滿足要求

...

直到找到一個不滿足要求2^k的為止，然後我們在[2^(k-1),2^k]區間內二分

這樣可以保證復雜度為O(nlognlog(limit/eps)) 不過常數巨大。。。。

居然直接A了 沒卡掉OJ真是差評

#include 
#include 
#include 
#include 
#include 
#include 
#define M 100100
#define EPS 1e-10
using namespace std;
typedef long double ld;
struct Point{
    ld x,y;
    Point() {}
    Point(ld _,ld __):
        x(_),y(__) {}
    friend istream& operator >> (istream &_,Point &p)
    {
        double x,y;
        scanf("%lf%lf",&x,&y);
        p.x=x;p.y=y;
        return _;
    }
    friend Point operator + (const Point &p1,const Point &p2)
    {
        return Point(p1.x+p2.x,p1.y+p2.y);
    }
    friend Point operator - (const Point &p1,const Point &p2)
    {
        return Point(p1.x-p2.x,p1.y-p2.y);
    }
    friend ld operator * (const Point &p1,const Point &p2)
    {
        return p1.x*p2.y-p1.y*p2.x;
    }
    friend Point operator * (const Point &p,ld rate)
    {
        return Point(p.x*rate,p.y*rate);
    }
    friend ld Distance(const Point &p1,const Point &p2)
    {
        return sqrt( (p1.x-p2.x)*(p1.x-p2.x) + (p1.y-p2.y)*(p1.y-p2.y) ) ;
    }
    friend Point Rotate(const Point &p)
    {
        return Point(-p.y,p.x);
    }
}points[M];
struct Line{
    Point p,v;
    Line() {}
    Line(const Point &_,const Point &__):
        p(_),v(__) {}
    friend Point Get_Intersection(const Line &l1,const Line &l2)
    {
        Point u=l1.p-l2.p;
        ld temp=(l2.v*u)/(l1.v*l2.v);
        return l1.p+l1.v*temp;
    }
};
struct Circle{
    Point o;
    ld r;
    Circle() {}
    Circle(const Point &_,ld __):
        o(_),r(__) {}
    bool In_Circle(const Point &p)
    {
        return Distance(p,o) < r + EPS ;
    }
};
int n,m;
Circle Min_Circle_Cover(int l,int r)
{
    static Point points[M];
    int i,j,k;
    Circle ans(Point(0,0),0);
    memcpy(points+l,::points+l,sizeof(Point)*(r-l+1));
    random_shuffle(points+l,points+r+1);
    for(i=l;i<=r;i++)
        if(!ans.In_Circle(points[i]))
        {
            ans=Circle(points[i],0);
            for(j=l;jlimit+EPS)
            break;
        if(i==n-pos+1) return n;
    }
    int l=pos+(i>>1)-1,r=pos+i-1;
    while(l+1>1;
        if(Min_Circle_Cover(pos,mid).rEPS)
    {
        ld mid=(l+r)/2;
        if( Judge(mid) )
            r=mid;
        else
            l=mid;
    }
    return r;
}
void Output(double limit)
{
    static Point stack[M];
    int i,last,top=0;
    for(i=1;i<=n;i=last+1)
    {
        last=Extend(i,limit);
        stack[++top]=Min_Circle_Cover(i,last).o;
    }
    cout<>n>>m;
    for(i=1;i<=n;i++)
        cin>>points[i];
    ld ans=Bisection();
    cout<