cjb-poi2011plot

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <cmath>
#define rep(i,n) for(int i=1;i<=n;i++)
#define mp make_pair
#define pb push_back
using namespace std;
#define PI 3.1415926535897932384626433
#define N 200010
#define LF double
int n,m,cnt;
LF R,eps=2e-8;
struct P{LF x,y;}a[N],poi[N],O,ans[N];
map<pair<int,int>,pair<LF,pair<LF,LF> > > fuck;
LF dis(P x,P y){return sqrt((x.x-y.x)*(x.x-y.x)+(x.y-y.y)*(x.y-y.y));}
P center(P x,P y,P z)
{
    LF a1=y.x-x.x,b1=y.y-x.y,
            c1=(a1*a1+b1*b1)/2.,a2=z.x-x.x,
            b2=z.y-x.y,c2=(a2*a2+b2*b2)/2.,
            d=a1*b2-a2*b1;
    return (P){x.x+(c1*b2-c2*b1)/d,x.y+(a1*c2-a2*c1)/d};
}
LF cal(int l,int r)
{
    if (fuck.find(mp(l,r))!=fuck.end())
        { 
            O=(P){fuck[mp(l,r)].second.first,fuck[mp(l,r)].second.second}; 
            return R=fuck[mp(l,r)].first; 
        }
    int i,j,k,n=0;
    for(i=l;i<=r;i++)a[n++]=poi[i];
    //for(i=0;i<n;i++)swap(a[rand()%n],a[i]);
    random_shuffle(a,a+n);
    for(O=a[0],R=0,i=1;i<n;i++)if(dis(a[i],O)>R+eps)
    for(O=a[i],R=0,j=0;j<i;++j)if(dis(a[j],O)>R+eps){
        O=(P){(a[i].x+a[j].x)/2.,(a[i].y+a[j].y)/2.},R=dis(O,a[i]);
        for(k=0;k<j;k++)if(dis(a[k],O)>R+eps)O=center(a[k],a[j],a[i]),R=dis(O,a[i]);
    }
    fuck[mp(l,r)]=mp(R,mp(O.x,O.y));
    return R;
}
int getnxt(int i,LF limit)
{
    int j;
    for(j=1;;j++)
    {
        cal(i,min(i+(1<<j)-1,n));
        if (R>limit+eps)break;
        if (i+(1<<j)-1>=n)return n;
    }
    int l=i+(1<<(j-1)),r=min(i+(1<<j)-1,n),mid;
    while (l<r)
    {
        mid=(l+r)>>1;
        cal(i,mid);
        if (R>limit+eps)r=mid; else l=mid+1;
    }
    return l-1;
}
bool check(LF limit)
{
    int i=1,j,now; cnt=0;
    while (i<=n)
    {
        if (cnt==m)return 0;
        j=getnxt(i,limit);
        cnt++;
        i=j+1;
    }
    return 1;
}
int main()
{
    scanf("%d%d",&n,&m);
    rep(i,n)scanf("%lf%lf",&poi[i].x,&poi[i].y);

    LF l=0,r=cal(1,n),mid;
    int lim=45;
    while (lim-- && r-l>eps)
    {
        mid=(l+r)/2;
        if (check(mid))r=mid; else l=mid;
    }
    printf("%.15lf\n%d\n",r,m);
    int j=1;
    rep(i,m)
    {
        if (j>n){ puts("0 0"); continue; }
        int nxt=getnxt(j,r);
        cal(j,nxt);
        printf("%.15lf %.15lf\n",O.x,O.y);
        j=nxt+1;
    }

    return 0;
}
}}}

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <cmath>
#define rep(i,n) for(int i=1;i<=n;i++)
#define mp make_pair
#define pb push_back
using namespace std;
#define PI 3.1415926535897932384626433
#define N 200010
#define LF double
int n,m,cnt;
LF R,eps=2e-8;
struct P{LF x,y;}a[N],poi[N],O,ans[N];
map<pair<int,int>,pair<LF,pair<LF,LF> > > fuck;
LF dis(P x,P y){return sqrt((x.x-y.x)*(x.x-y.x)+(x.y-y.y)*(x.y-y.y));}
P center(P x,P y,P z)
{
    LF a1=y.x-x.x,b1=y.y-x.y,
            c1=(a1*a1+b1*b1)/2.,a2=z.x-x.x,
            b2=z.y-x.y,c2=(a2*a2+b2*b2)/2.,
            d=a1*b2-a2*b1;
    return (P){x.x+(c1*b2-c2*b1)/d,x.y+(a1*c2-a2*c1)/d};
}
LF cal(int l,int r)
{
    if (fuck.find(mp(l,r))!=fuck.end())
        { 
            O=(P){fuck[mp(l,r)].second.first,fuck[mp(l,r)].second.second}; 
            return R=fuck[mp(l,r)].first; 
        }
    int i,j,k,n=0;
    for(i=l;i<=r;i++)a[n++]=poi[i];
    //for(i=0;i<n;i++)swap(a[rand()%n],a[i]);
    random_shuffle(a,a+n);
    for(O=a[0],R=0,i=1;i<n;i++)if(dis(a[i],O)>R+eps)
    for(O=a[i],R=0,j=0;j<i;++j)if(dis(a[j],O)>R+eps){
        O=(P){(a[i].x+a[j].x)/2.,(a[i].y+a[j].y)/2.},R=dis(O,a[i]);
        for(k=0;k<j;k++)if(dis(a[k],O)>R+eps)O=center(a[k],a[j],a[i]),R=dis(O,a[i]);
    }
    fuck[mp(l,r)]=mp(R,mp(O.x,O.y));
    return R;
}
int getnxt(int i,LF limit)
{
    int j;
    for(j=1;;j++)
    {
        cal(i,min(i+(1<<j)-1,n));
        if (R>limit+eps)break;
        if (i+(1<<j)-1>=n)return n;
    }
    int l=i+(1<<(j-1)),r=min(i+(1<<j)-1,n),mid;
    while (l<r)
    {
        mid=(l+r)>>1;
        cal(i,mid);
        if (R>limit+eps)r=mid; else l=mid+1;
    }
    return l-1;
}
bool check(LF limit)
{
    int i=1,j,now; cnt=0;
    while (i<=n)
    {
        if (cnt==m)return 0;
        j=getnxt(i,limit);
        cnt++;
        i=j+1;
    }
    return 1;
}
int main()
{
    scanf("%d%d",&n,&m);
    rep(i,n)scanf("%lf%lf",&poi[i].x,&poi[i].y);
    LF l=0,r=cal(1,n),mid;
    int lim=45;
    while (lim-- && r-l>eps)
    {
        mid=(l+r)/2;
        if (check(mid))r=mid; else l=mid;
    }
    printf("%.15lf\n%d\n",r,m);
    int j=1;
    rep(i,m)
    {
        if (j>n){ puts("0 0"); continue; }
        int nxt=getnxt(j,r);
        cal(j,nxt);
        printf("%.15lf %.15lf\n",O.x,O.y);
        j=nxt+1;
    }
    return 0;
}