uva 1421

稍微有点新意的二分

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<iostream>
#define eps 0.000001
#define maxn 5005
using namespace std;
int n;
double w;
struct node
{
double x,y,d;
bool operator<(const node &t)const
{
return d<t.d;
}
} no[maxn]; int get(double x)
{
double ll=atan2(no[].d,no[].y-x),rr=atan2(no[].d,no[].x-x);
for(int i=;i<n;i++)
{
double l=atan2(no[i].d,no[i].y-x);
double r=atan2(no[i].d,no[i].x-x);
// printf("%lf %lf++\n",l,r);
if(l-rr>eps)return ;
if(r-ll<-eps)return -;
ll=max(ll,l);
rr=min(rr,r);
}
return ;
} bool solve()
{
double l=0.0,r=w;
while(r-l>eps)
{
double mid=(r+l)/2.0;
int k=get(mid);
if(k==)return ;
else if(k==)l=mid;
else r=mid;
}
return ;
} int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%lf",&w);
scanf("%d",&n);
for(int i=; i<n; i++)
{
scanf("%lf%lf%lf",&no[i].d,&no[i].x,&no[i].y);
}
sort(no,no+n); if(solve())puts("YES");
else puts("NO");
}
return ;
}
上一篇:Mybatis中#与$区别


下一篇:作业6-COSPLAY孩子他家长