{题解}[jzoj3636]【BOI2012】Mobile(mobile)

传送门

Analysis

比较容易想到 把原题转化为判定问题 比如说 对于一个ans 对每个点画圆 判断是否覆盖整条线段

显然 二分是过不了的 邪恶的出题人做了很多事情 比如说 500ms SPJ 假装不卡精度 100个数据点

于是 草稿纸上就有了下面这张图 可以看到 这些园之间有交集 当然是希望两两交集尽量小的 于是可以两两考虑极限下 两者交集最小的值 然后随便搞搞好了

具体实现中 可以使用中垂线的性质 拿中垂线求个交点一类的 至于如何求交点的话 db perbis(Dot x,Dot y) {return ((sqr(x.x) - sqr(y.x) + sqr(x.y) - sqr(y.y)) / (2 * (x.x - y.x)));} 不算太难 但很难一步想到中垂线

Code

#include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define oo (db)99999999999999 #define abs(x) (((x)>=0)?(x):(-(x))) #define fo(i,x,y) for (ll i = (x);i <= (y);++ i) #define fd(i,x,y) for (ll i = (x);i >= (y);-- i) using namespace std; typedef long long ll; typedef double db; const ll N = 1001000,NM = 1e15,Prec = 1e4; struct Dot{ db x,y; Dot(db x_ = 0,db y_ = 0){x = x_,y = y_;} }a[N]; ll n,L,m; db tmp,ans; ll sta[N],hd,tl; db read(db &n) { char ch=' ';db q=0,w=1; for(;(ch!='-')&&((ch<'0')||(ch>'9'));ch=getchar()); if(ch=='-')w=-1,ch=getchar(); for(;ch>='0' && ch<='9';ch=getchar())q=q*10+ch-48;n=q*w;return n; } inline db sqr(db x) {return ((x)*(x));} inline db max(db x,db y) {return (((x)>(y))?(x):(y));} inline db min(db x,db y) {return (((x)<(y))?(x):(y));} db perbis(Dot x,Dot y) {return ((sqr(x.x) - sqr(y.x) + sqr(x.y) - sqr(y.y)) / (2 * (x.x - y.x)));} int main() { freopen("mobile.in","r",stdin); freopen("mobile.out","w",stdout); scanf("%lld%lld", &n, &L); //a[m = 1] = Dot(0,0); fo(i,1,n) { db x,y; read(x),read(y); if (x != a[m].x) a[++ m] = Dot(x,y); else if (x == a[m].x && (abs(y) < abs(a[m].y))) a[m] = Dot(x,y); } //a[++ m] = Dot(L,0); n = m; tmp = oo * oo; fo(i,1,n) if (sqr(a[i].x) + sqr(a[i].y) < tmp * tmp) tmp = sqrt(sqr(a[i].x) + sqr(a[i].y)); ans = tmp, tmp = oo * oo; fo(i,1,n) if (sqr(a[i].x - L) + sqr(a[i].y) < tmp * tmp) tmp = sqrt(sqr(a[i].x - L) + sqr(a[i].y)); ans = max(ans,tmp); sta[1] = tl = hd = 1; fo(i,2,n) { while (hd < tl && perbis(a[sta[hd]],a[sta[hd + 1]]) < 0) ++ hd; while (hd < tl && perbis(a[sta[tl]],a[sta[tl - 1]]) > perbis(a[i],a[sta[tl]])) -- tl; sta[++ tl] = i; } fo(i,hd,tl - 1) { db p = perbis(a[sta[i]],a[sta[i + 1]]); if (p > L) break; tmp = sqrt(sqr(a[sta[i]].x - p) + sqr(a[sta[i]].y)); ans = max(ans,tmp); } printf("%lf", ans); }