内容目录
众所周知,精度误差是很坑人的东西
而且有的时候有了eps反而会错(考虑你的条件是严苛还是放宽)
从 0 到 x0 的覆盖中,点的排序就是一例
:
首先要尽可能以x排序,然后左端点尽量靠右
但是左端点会爆误差……所以先考虑 端点的误差是否可以忽略,如果不行就算相等)
第二处是排序的对象
理论上是从0到x0 不合条件的都被赋0了……
但是 有可能出现 0<x0<a[i].x<a[i+7].x这样的 整条线段不在里面的情况 此时若用max min 那么 会忽略左端点 (我们的本意是让不在区间内的点的区间删了-要删就全删)
故 需考虑·这样的情况
<-最右边的黄色和青色的
第三处是答案(终极精度误差) 你要让最左端点<eps和最右端点<x0-eps 这里的限制应为严苛(倘若放宽,最左端点为0(前面已经让它∈[0.x0])都不行的话 会出现永远不可能的情况
#include<iostream> #include<cstring> #include<cstdio> #include<cstdlib> #include<cmath> #include<functional> #include<algorithm> using namespace std; #define MAXX (10000+10) #define MAXH (100+10) #define MAXN (2*7+10) double h,x0,m; const double eps=1e-10; bool cmp(const double a,const double b); bool equal(const double a,const double b) { if (-eps<a-b&&a-b<eps) return 1; else return 0; } struct node //表示线段端点 y=1表示左端点 y=-1有端点 { double x,y; node():x(0.0),y(0.0){} node(double _x,double _y):x(_x),y(_y){} friend bool operator<(const node a,const node b){return equal(a.x,b.x)?a.y>b.y:cmp(a.x,b.x);/*(a.y!=b.y)?a.y>b.y:a.x+eps<b.x||a.x-eps<b.x;*/ /* ? */ } }a[MAXN]; double x[MAXN],r[MAXN]; bool cmp(const double a,const double b) { // cout<<(a-eps<b)<<endl; return ((a-eps<b)||(a+eps<b)); } bool is_ok(double m) { for (int i=1;i<=7;i++) { if (h<=r[i]+m) { double dis=sqrt(pow((r[i]+m),2)-pow((h),2)); // if (dis<0) cout<<dis<<' '; a[i].x=max(0.0,x[i]-dis);a[i+7].x=min(x0,x[i]+dis); // if (max(0.0,x[i]-dis)>min(x0,x[i]+dis)) cout<<x[i]-dis<<' '<<x[i]+dis; } else a[i].x=a[i+7].x=0; if (a[i].x>a[i+7].x) a[i].x=a[i+7].x=0; a[i].y=1;a[i+7].y=-1; } // for (int i=1;i<=14;i++) cout<<a[i].x<<' '<<a[i].y<<endl; sort(a+1,a+1+14); // for (int i=1;i<=14;i++) cout<<a[i].x<<' '<<a[i].y<<endl; for (int i=1,j=0;i<14;i++) { j+=a[i].y; if (!j) return 0; } // if (cmp(0.0,a[1].x)||cmp(a[14].x,x0)) return 0; if ((eps<a[1].x)||(a[14].x<x0-eps)) return 0; return 1; } int main() { // freopen("rainbow.in","r",stdin); scanf("%lf%lf",&h,&x0); for (int i=1;i<=7;i++) scanf("%lf%lf",&x[i],&r[i]); // for (int i=1;i<=7;i++) cout<<r[i]<<' '; /* node a=node(3.0,-1.0); node b=node(2.0,-1.0); cout<<(a<b)<<endl; */ double l=0.0,r=x0+h+1; // cout<<is_ok(60.0); while (r-l>eps) { double m=(l+r)/2; if (is_ok(m)) r=m; else l=m; } printf("%.2lfn",r); // while (1); return 0; }