首页 > 代码库 > Bzoj2280 [Poi2011]Plot

Bzoj2280 [Poi2011]Plot

Time Limit: 300 Sec  Memory Limit: 128 MBSec  Special Judge
Submit: 392  Solved: 79

Description

给出一系列点p_1, p_2, ... , p_n,将其分成不多余m个连续的段,第i段内求一个点q_i,使得q_i到这段内点的距离的最大值的最大值最小

 

Input

第一行,n m
下面n行,每行两个整数,表示p_i的x y坐标
1<=m<=n<=100000
坐标范围[-1000000,1000000] 0<p,q,r<=150,输入中至少包含一个’N’

 

Output

第一行,q_i到这段内点的距离的最大值的最大值的最小值
第二行,分成的段数k
下面k行,每行两个实数,表示q_k的x y坐标


All the real numbers should be printed with at most 15 digits after the decimal point. 

Sample Input

7 2
2 0
0 4
4 4
4 2
8 2
11 3
14 2

Sample Output

3.00000000
2
2.00000000 1.76393202
11.00000000 1.99998199

HINT

 

wyx528提供SPJ

 

Source

 

数学问题 计算几何 随机增量法 + 二分答案

 

出题人丧心病狂系列。

刚开始没看数据,还以为是一维的DP……

如果已知要求哪些点放在同一段的话,是一个最小圆覆盖问题。

然后发现放在同一段的必须是原序列中连续的一些点,那么可以二分答案+贪心覆盖。

贪心的时候要二分判断最远能覆盖到多远 ←但是由于常数巨大,二分也太慢了,需要先倍增,倍增不动了再二分。

剩下的就是卡精度+卡常数。

在随机增量函数里把一个变量a写成了p,竟然还过了前几组数据,以至于我坚定地认为是计算精度有问题,各种卡精度

当发现这个错误的时候,代码已经被照着别人的题解改得面目全非……

 

最后——

卡评测姬真™开心!

那种整个列表都是pending,所有人等着你一个人评测,而你并没有恶意卡评测姬不怕别人怼的感觉真是太棒辣 (光速逃

 

  1 #include<iostream>  2 #include<algorithm>  3 #include<cstring>  4 #include<cstdio>  5 #include<cmath>  6 //#include<ctime>  7 #define LL long long  8 using namespace std;  9 const long double eps=1e-10; 10 const int mxn=100010; 11 int read(){ 12     int x=0,f=1;char ch=getchar(); 13     while(ch<0 || ch>9){if(ch==-)f=-1;ch=getchar();} 14     while(ch>=0 && ch<=9){x=x*10+ch-0;ch=getchar();} 15     return x*f; 16 } 17 struct point{ 18     long double x,y; 19     point(){} 20 //    point(double _x,double _y):x(_x),y(_y){} 21     point(long double _x,long double _y):x(_x),y(_y){} 22     point operator + (const point &b){return point(x+b.x,y+b.y);} 23     point operator - (const point &b){return point(x-b.x,y-b.y);} 24     long double operator * (const point &b){return x*b.x+y*b.y;} 25 //    point operator * (const long double v){return point(x*v,y*v);} 26     point operator / (const long double v){return point(x/v,y/v);} 27 }p[mxn]; 28 inline int DT(long double x){ 29     if(fabs(x)<eps)return 0; 30     return x<0?-1:1; 31 } 32 inline long double sqr(long double x){return x*x;} 33 inline long double dist(point a,point b){ 34     return sqrt(sqr(a.x-b.x)+sqr(a.y-b.y)); 35 } 36 /* 37 inline double dist(point &a,point &b){ 38     return sqrt((a-b)*(a-b)); 39 } 40 */ 41 inline point cir(point &p1,point &p2,point &p3){ 42     long double a=2*(p2.x-p1.x),b=2*(p2.y-p1.y); 43     long double c=p2*p2-p1*p1; 44     long double d=2*(p3.x-p1.x),e=2*(p3.y-p1.y); 45     long double f=p3*p3-p1*p1; 46     point O;O.x=(b*f-e*c)/(b*d-e*a);O.y=(d*c-a*f)/(b*d-e*a); 47     return O; 48 } 49 int n,m; 50 point ans[mxn],CI;int top=0; 51 point a[mxn]; 52 long double check(int L,int R){ 53     for(int i=L;i<=R;i++)a[i]=p[i]; 54     random_shuffle(a+L,a+R+1); 55     int i,j,k; 56     long double r=0;point C=a[L]; 57     for(i=L+1;i<=R;i++)if(DT(dist(C,a[i])-r)>0){ 58         C=a[i];r=0; 59         for(j=L;j<i;j++)if(DT(dist(C,a[j])-r)>0){ 60             C=(a[i]+a[j])/2; 61             r=dist(C,a[j]); 62             for(k=L;k<j;k++) 63                 if(DT(dist(C,a[k])-r)>0){ 64                     C=cir(a[i],a[j],a[k]); 65                     r=dist(C,a[i]); 66                 } 67         } 68     } 69     CI=C; 70     return r; 71 } 72 int calc(int s,int now,long double lim){ 73     int i; 74     for(i=1;;i=min(n-s+1,i<<1)){ 75         long double r=check(s,s+i-1); 76         if(r<lim+eps){ans[now]=CI;} 77             else break; 78         if(i==n-s+1)return n; 79     } 80     int l=s+(i>>1)-1,r=s+i-1,mid; 81     while(l+1<r){ 82         mid=(l+r)>>1; 83         long double R=check(s,mid); 84         if(DT(R-lim)<=0){ 85             ans[now]=CI; 86             l=mid; 87         }else r=mid; 88     } 89     return l; 90 } 91 bool solve(double lim){ 92     top=0; 93     for(int i=1,ed=i;i<=n && top<=m;i=ed+1){ 94         top++; 95         ed=calc(i,top,lim); 96     } 97     return (top<=m); 98 } 99 int main(){100 //    freopen("in.txt","r",stdin);101     int i,j;102     srand(19260817);103     n=read();m=read();104     for(i=1;i<=n;i++){105         scanf("%Lf%Lf",&p[i].x,&p[i].y);106     }107     long double l=0,r=check(1,n);int cnt=0;108     while(r-l>eps){109         cnt++;110         if(cnt>45)break;111         long double mid=(l+r)/2;112         if(solve(mid))r=mid;113         else l=mid;114     }115     solve(r+eps);116     printf("%.15lf\n",(double)r+1e-10);117     printf("%d\n",top);118     for(i=1;i<=top;i++){119         printf("%.15Lf %.15Lf\n",ans[i].x,ans[i].y);120     }121     return 0;122 }

 

Bzoj2280 [Poi2011]Plot