Loading... ## 题意 给定平面上 $n$ 个点和 $a$。设 $P(a,0),Q(-a,0)$。要求找出一条直线 $l$ 过至少两个给定点,最小化 $\max\{ |PX-QX|\},X\in l$。 $n\le10^5,a\le 10^4$。 ## 题解 ### 计算 首先我们来看看,假如确定某两个点 $\max\{ |PX-QX|\},X\in l$ 这个东西是怎么算的,根据将军饮马的知识  第一种情况 $PQ$ 在 $l$ 同侧,观察 $\Delta PQX$ 可得,$PX-QX\leq PQ$,所以可得,$\max\{ |PX-QX|\}=PQ,X\in l$。  第二种情况 $PQ$ 在 $l$ 异侧,故做 $P$ 关于 $l$ 的对称点 $P'$,观察 $\Delta P'QX$ 可得,$PX-QX=P'X-QX\leq P'Q$,所以可得,$\max\{ |PX-QX|\}=P'Q,X\in l$。 ### 解题 由于答案最大就是 $2a$,所以不需要特别考虑第二种情况。现在只计算第一种情况,最大最小值直接套路用二分答案,若当前二分 $mid$ 这个答案,考虑怎么 check。这样二分的几何意义就是某一个 $P'$ 点在以 $Q$ 为圆心,半径为 $mid$ 圆内,记这个圆为圆 $Q$。进而考虑 $P'$ 怎么转化,就是以 $A$ 为圆心 $AP$ 为半径的圆和以 $B$ 为圆心 $BP$ 为半径的圆的其中一个交点,分别记为圆 $A,B$,那么这样转化的好处是把 $A,B$ 贡献拆分开了,两个圆是独立的。现在记圆 $Q$ 在圆 $A,B$ 内的弧分别为 $\overset{\LARGE{\frown}}{A},\overset{\LARGE{\frown}}{B}$,那么两个圆的交点在 $Q$ 可以转化为 $\overset{\LARGE{\frown}}{A}$ 和 $\overset{\LARGE{\frown}}{B}$ 是有交,但是可能圆 $A,B$ 是包含关系,所以 $\overset{\LARGE{\frown}}{A}$ 和 $\overset{\LARGE{\frown}}{B}$ 不能是包含关系。这个很好判和括号序差不多,求出圆 $A,B$ 和圆 $Q$ 的交点和圆心到交点的向量幅角,用栈判断就可以了。这个过程不好理解可以看我[画的 GeoGebra](https://www.geogebra.org/m/pcsmpk8k)。 ```cpp #include<bits/stdc++.h> // #define ONLINE_JUDGE #define INPUT_DATA_TYPE int #define OUTPUT_DATA_TYPE int inline __attribute((always_inline)) INPUT_DATA_TYPE read(){register INPUT_DATA_TYPE x=0;register char f=0,c=getchar();while(c<'0'||'9'<c)f=(c=='-'),c=getchar();while('0'<=c&&c<='9')x=(x<<3)+(x<<1)+(c&15),c=getchar();return f?-x:x;}void print(OUTPUT_DATA_TYPE x){if(x<0)x=-x,putchar('-');if(x>9)print(x/10);putchar(x%10^48);return;} struct point{ double x,y; point operator + (const point &o) const {return {x+o.x,y+o.y};} point operator - (const point &o) const {return {x-o.x,y-o.y};} point operator * (const double &o) const {return {x*o,y*o};} }; struct circle{ point o; double r; }a[100010]; double moo(point a){return std::sqrt(a.x*a.x+a.y*a.y);} double dist(point a,point b){return moo(a-b);} point unit(point a){return a*(1.0/moo(a));} double polarAngle(point a){return atan2(a.y,a.x);} auto intersect(circle a,circle b){ double d=dist(a.o,b.o); double x=(a.r*a.r+d*d-b.r*b.r)/(d*2); double z=std::sqrt(a.r*a.r-x*x); point u=unit(b.o-a.o); point mid=a.o+u*x; std::swap(u.x,u.y),u.x*=-1; return std::make_pair(mid+u*z,mid-u*z); } point p,q; int n; bool check(double mid){ register int i; register double d; std::vector<std::pair<double,int>> vec; std::stack<int> S; circle o={p,mid}; for(i=0;i<n;++i){ d=dist(o.o,a[i].o); if(o.r+a[i].r>d&&fabs(o.r-a[i].r)<d){ auto tmp=intersect(o,a[i]); vec.push_back({polarAngle(tmp.first-o.o),i}); vec.push_back({polarAngle(tmp.second-o.o),i}); } } std::sort(vec.begin(),vec.end()); for(auto val:vec) if(S.empty()||S.top()!=val.second) S.push(val.second); else S.pop(); return !S.empty(); } int main(){ #ifndef ONLINE_JUDGE freopen("name.in", "r", stdin); freopen("name.out", "w", stdout); #endif register int i; register double l,r,mid; n=read(); int aa=read(); p.x=aa,q.x=-aa; for(i=0;i<n;++i) a[i].o.x=read(),a[i].o.y=read(),a[i].r=dist(a[i].o,q); l=0,r=dist(p,q); for(i=0;i<50;++i){ mid=(l+r)/2; if(check(mid)) r=mid; else l=mid; } printf("%.10lf",l); #ifndef ONLINE_JUDGE fclose(stdin); fclose(stdout); #endif return 0; } ``` 最后修改:2024 年 04 月 21 日 © 允许规范转载 打赏 赞赏作者 赞 如果觉得我的文章对你有用,请随意赞赏