Codeforces 832C

832C - Strange Radiation

思路：二分最短时间。

代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair 
#define pi acos(-1.0)
#define pii pair<int,int>
#define pil pair<int,long>
#define mem(a,b) mamset(a,b,sizeof(a))

const int MOD=1e9+7;
const int INF=0x3f3f3f3f;
const int N=1e5+5;
const double eps=1e-9;

int n;
double s;

struct people
{
    double x,v,t;
}a[N];

bool check(double t)
{
    bool flag1=false,flag2=false;
    double l_l=1e6,l_r=0,r_l=1e6,r_r=0;
    for(int i=0;i<n;i++)
    {
        if(a[i].t==1)
        {
            if(a[i].x-(a[i].v+s)*t>0)continue;//如果炸弹放在这个点上都到不了，说明这个人肯定到不了。 
            flag1=true;
            if(a[i].x-a[i].v*t<=0)//如果不加速也能到，那说明炸弹放在哪里都可以。 
            {
                l_l=0;
                l_r=1e6;
                continue;
            }
            double X=floor((t*(s*s-a[i].v*a[i].v)+a[i].x*a[i].v)/s);
            l_r=max(l_r,X);//取并集 
            l_l=min(l_l,(double)a[i].x);
        }
        else if(a[i].t==2)
        {
            if(a[i].x+(a[i].v+s)*t<1e6)continue;
            flag2=true;
            if(a[i].x+a[i].v*t>=1e6)
            {
                r_l=0;
                r_r=1e6;
                continue;
            }
            double X=ceil((1e6*(s-a[i].v)-t*(s*s-a[i].v*a[i].v)+a[i].x*a[i].v)/s);
            r_l=min(r_l,X);
            r_r=max(r_r,(double)a[i].x); 
        }
    }
    if(!flag1||!flag2)return false;
    if(l_l>l_r||r_l>r_r)return false;
    if(l_r<r_l||r_r<l_l)return false;//取交集 
    return true;
}

int main()
{
    scanf("%d%lf",&n,&s);
    for(int i=0;i<n;i++)
    scanf("%lf%lf%lf",&a[i].x,&a[i].v,&a[i].t);
    
    double l=0,r=1e6+5;
    double mid=(l+r)/2;
    while(r-l>=eps)
    {
        if(check(mid))r=mid;
        else l=mid;
        mid=(l+r)/2;
    }
    printf("%.12lf
",mid);
    return 0;
}