题目中出现了至多和最小等字眼,因此很有可能需要使用二分答案。
怎么进行二分呢?我们对 dd 进行二分并检验当前 d 值是否符合题意。不难发现,如果一个点到原点的距离不超过 d,那么这个点一定符合(所有正比例函数都经过原点)。因此我们只需考虑 x2+y2>d2 的点。
由于到一个点距离不超过 d 的集合就是以该点为圆心,d 为半径的圆内,因此我们只需要求出该圆过原点的两条切线的斜率即可。显然在这两条直线 y=Lx 和 y=Rx 之间(不一定是斜率之间)的所有直线都是符合题意的:

我们只需要找到这 n 个点对应的 L,R 值,将这些点的 [L,R] 抽象成 n 条线段,就可以把问题转化成用最少的点覆盖所有线段的经典贪心问题,并以最少的点数是否小于等于 k 作为二分答案的判断条件。
那么最关键的就是如何求解每个点的 L,R。这里有三种方法:
Solution 1 二分套二分
为什么题目要提供点和直线的距离公式呢?实际上,根据之前插图的演示,不难发现直线与点的距离满足一定的单调性。我们可以利用这个性质再一次二分,得到 L,R 的值。
对于斜率等于 +∞ 的情形,我们可以直接在二分前进行处理,例如将其修改成一个足够大的数。
该做法的时间复杂度为 O(nlogxlogx+nlognlogx)(x 为二分区间大小):
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87
| #include<bits/stdc++.h> using namespace std; int n,k; long double l,r=100000,ans; struct point { long double x,y; }p[25001]; struct interval { long double L,R; bool operator<(const interval &x)const { return R<x.R; } }a[25001]; bool check_dis(int x,int y,long double k,long double d) { long double dis=fabs(y-k*x)/sqrt(k*k+1); return dis<=d; } interval get(point p,long double d) { if(!p.x)return (interval){-p.y/d,p.y/d}; interval ans; long double l=0,r=p.y/p.x; while(l<=r) { long double mid=(l+r)*0.5; if(check_dis(p.x,p.y,mid,d)) { r=mid-0.00000001; ans.L=mid; } else l=mid+0.00000001; } l=p.y/p.x,r=100000; while(l<=r) { long double mid=(l+r)*0.5; if(check_dis(p.x,p.y,mid,d)) { l=mid+0.00000001; ans.R=mid; } else r=mid-0.00000001; } return ans; } bool check(long double d) { int cnt=0; for(int i=1;i<=n;++i) { if(sqrt(p[i].x*p[i].x+p[i].y*p[i].y)<=d)continue; a[++cnt]=get(p[i],d); } sort(a+1,a+cnt+1); int tot=0; long double tmp=0; for(int i=1;i<=cnt;++i) { if(tmp<=a[i].L) { tmp=a[i].R; if(++tot>k)return false; } } return true; } int main() { scanf("%d%d",&n,&k); for(int i=1;i<=n;++i)scanf("%Lf%Lf",&p[i].x,&p[i].y); while(l<=r) { long double mid=(l+r)*0.5; if(check(mid)) { r=mid-0.0001; ans=mid; } else l=mid+0.0001; } printf("%.2Lf",ans); return 0; }
|
Solution 2 二分+导角
我们可以通过角和斜率之间的转化求解。
考虑下图的情形(两条直线斜率都非负):

我们可以用反正切函数求出 PO 与 x 轴正方向的夹角 α,用反正弦函数求出 β=∠TOP。由于两条切线与 OP 之间的夹角相等,因此两条切线与 x 轴正半轴的夹角为 α±β。
我们还需考虑下面两种情形:


这种情形下切线斜率一正一负,而这此时直接把负的当左端点、正的当右端点显然是错误的(有一个跨 0 的过程)。又因为题中没有负坐标,因此只需要保留正斜率。那么:
- 在第一种情形中,符合题意的所有斜率的最小值为其中的正斜率,最大值为 +∞。
- 在第二种情形中,最小值为 0,最大值为其中的正斜率。
考虑当前的点属于哪一种情形:
- 当切点位于第二象限时(此时 α+β>90∘),属于第一种。
- 当切点位于第四象限时(此时 α+β<90∘),属于第二种。
那么,为什么二分套二分的方法不需要对此进行考虑呢?这是因为,我们可以在求解 L,R 时将二分下界设为 0,这样就避免了需要讨论负斜率的情况。
该做法的时间复杂度为 O(nlogx+nlogn):
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71
| #include<bits/stdc++.h> using namespace std; const double rt=acos(-1)*0.5; int n,k; long double l,r=100000,ans; struct point { long double x,y; }p[25001]; struct interval { long double L,R; bool operator<(const interval &x)const { return R<x.R; } }a[25001]; bool check(long double d) { int cnt=0; for(int i=1;i<=n;++i) { long double x=p[i].x,y=p[i].y; if(x*x+y*y<=d*d)continue; ++cnt; long double alpha,beta; alpha=atan(y/x); if(!x)alpha=rt; beta=asin(d/sqrt(x*x+y*y)); a[cnt].L=tan(alpha-beta),a[cnt].R=tan(alpha+beta); if(a[cnt].L>a[cnt].R)swap(a[cnt].L,a[cnt].R); if(a[cnt].L<0) { if(alpha+beta>rt) { a[cnt].L=a[cnt].R; a[cnt].R=1e18; } else a[cnt].L=0; } } sort(a+1,a+cnt+1); int tot=0; long double tmp=0; for(int i=1;i<=cnt;++i) { if(tmp<=a[i].L) { tmp=a[i].R; if(++tot>k)return false; } } return true; } int main() { scanf("%d%d",&n,&k); for(int i=1;i<=n;++i)scanf("%Lf%Lf",&p[i].x,&p[i].y); while(l<=r) { long double mid=(l+r)*0.5; if(check(mid)) { r=mid-0.0001; ans=mid; } else l=mid+0.0001; } printf("%.2Lf",ans); return 0; }
|
Solution 3 二分+导边
借助之前的示意图:

不妨设 T 的坐标为 (a,b),则 OT 的斜率为 ba,TP 的斜率为 −ab。把 P(x,y) 和 T(a,b) 代入得 b−ya−x=−ab。化简得 a2+b2=ax+by。
又因为 TP=d,因此有 (x−a)2+(y−b)2=d2。化简得 a2+b2−2ax−2by=d2−x2−y2。
由于 x,y,d 为常数,因此可设 c=d2−x2−y2。
因此
{a2+b2=ax+by(1)a2+b2−2ax−2by=c(2)
把 (1) 代入 (2) 得
ax+by=−c
因此我们可以将 b 用 a 进行表示(仅在 y≠0 时成立):
b=−c−axy
再代回 (1) 得:
a2+(c+ax)2y2=−c
a2y2+c2+2acx+a2x2+cy2=0
(x2+y2)a2+2cxa+c2+cy2=0
a1,2=−2cx±√4c2x2−4(x2+y2)(c2+cy2)2(x2+y2)
=−cx±√c2x2−(x2+y2)(c2+cy2)x2+y2
=−cx±√−cx2y2−y2c2−cy4x2+y2
=−cx±y√−c(x2+y2+c)x2+y2
最后求出 b1,2 即可得到两条直线的斜率。
特判 y=0 的情形:

此时 OP=x,TP=d,OT=√x2−d2。
作 TH⊥OP 于 H,则 sin∠TOH=TPOP=THOT。因此 dx=TH√x2−d2,即 TH=d√x2−d2x。然后再在 △OTH 中用一次勾股定理即可求出 OH。最后斜率即为 THOH。
由于 y=0,因此较下方的切线的斜率必然为负。之前提到了本题无需考虑负斜率,因此取斜率的最小值为 0,最大值为 THOH 即可。
x=0 的情形不需单独考虑,因为其斜率的范围显然为 [−yd,yd],适用于一般情况。
与导角的方法类似,我们仍需考虑这两种情形:


考虑每个点属于哪一种情形:
- 当负斜率的切点位于 y 轴上方时,第一种情形成立。
- 当负斜率的切点位于 y 轴下方时,第二种情形成立。
相比于导角的做法,该做法时间复杂度仍为 O(nlogx+nlogn),但不涉及反三角函数的使用,因此常数较小:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86
| #include<bits/stdc++.h> using namespace std; int n,k; long double l,r=100000,ans; struct point { long double x,y; }p[25001]; struct interval { long double L,R; bool operator<(const interval &x)const { return R<x.R; } }a[25001]; bool check(long double d) { int cnt=0; for(int i=1;i<=n;++i) { long double x=p[i].x,y=p[i].y; if(x*x+y*y<=d*d)continue; ++cnt; if(!y) { a[cnt].L=0; long double b1=d*sqrt(x*x-d*d)/x; long double a1=sqrt(x*x-d*d-b1*b1); a[cnt].R=b1/a1; } else { long double c=d*d-x*x-y*y,delta=-c*(x*x+y*y+c); long double a1=(-c*x+y*sqrt(delta))/(x*x+y*y); long double a2=(-c*x-y*sqrt(delta))/(x*x+y*y); long double b1=(-c-a1*x)/y,b2=(-c-a2*x)/y; a[cnt].L=b1/a1,a[cnt].R=b2/a2; if(a[cnt].L>a[cnt].R) { swap(a[cnt].L,a[cnt].R); swap(a1,a2); swap(b1,b2); } if(a[cnt].L<0) { if(b1>0) { a[cnt].L=a[cnt].R; a[cnt].R=1e18; } else a[cnt].L=0; } } } sort(a+1,a+cnt+1); int tot=0; long double tmp=0; for(int i=1;i<=cnt;++i) { if(tmp<=a[i].L) { tmp=a[i].R; if(++tot>k)return false; } } return true; } int main() { scanf("%d%d",&n,&k); for(int i=1;i<=n;++i)scanf("%Lf%Lf",&p[i].x,&p[i].y); while(l<=r) { long double mid=(l+r)*0.5; if(check(mid)) { r=mid-0.0001; ans=mid; } else l=mid+0.0001; } printf("%.2Lf",ans); return 0; }
|