问题

https://vjudge.net/problem/UVA-1421

分析

参考：https://www.baidu.com/link?url=_97SeoEnptxHUjm7w30zPkV7cwJLuiQoKvbiADlHIWl2-U3imQIzyhtH1rbldN6OXdv3L3eVTvhQfuE2UgVjTK&wd=&eqid=ff3194ad00016a44000000055e6f8f8a
二分法的应用，使用二分来确定应该左移还是右移

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long LL;
const int maxn=5000+5;
const double eps=1e-6;
struct Target{int d,l,r;bool operator < (const Target &rhs) const {return d<rhs.d;}
}tar[maxn];
int T,w,n,s,kase=0,a[maxn],b[maxn];int judge(double cur){//k=1/tan(theta)double k1=(tar[0].l-cur)/tar[0].d,k2=(tar[0].r-cur)/tar[0].d,k3,k4;for(int i=1;i<n;++i){k3=(tar[i].l-cur)/tar[i].d;k4=(tar[i].r-cur)/tar[i].d;if(k3-k2>eps) return -1;  //点要左移else if(k4-k1<-eps) return 1;  //要右移k1=max(k1,k3);k2=min(k2,k4);}return 0;
}bool solve(){double L=0,R=w;while(R-L>eps){double mid=(L+R)/2;int t=judge(mid);if(t==0) return true;else if(t==1){L=mid;}else{R=mid;}}return false;
}int main(void){scanf("%d",&T);while(T--){scanf("%d%d",&w,&n);for(int i=0;i<n;++i){scanf("%d%d%d",&tar[i].d,&tar[i].l,&tar[i].r);}sort(tar,tar+n);bool ans=solve();printf("%s\n",ans?"YES":"NO");}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！