Slalom

题意：

有n个宽度为w的门，给出门的左端点的水平位置x和高度y，和恒定的垂直速度，现有s个速度，求能通过这n个门的最大速度。

分析：

二分速度判断

#include <map>

#include <set>

#include <list>

#include <cmath>

#include <queue>

#include <stack>

#include <cstdio>

#include <vector>

#include <string>

#include <cctype>

#include <complex>

#include <cassert>

#include <utility>

#include <cstring>

#include <cstdlib>

#include <iostream>

#include <algorithm>

using namespace std;

typedef pair<int,int> PII;

typedef long long ll;

#define lson l,m,rt<<1

#define pi acos(-1.0)

#define rson m+1,r,rt<<11

#define All 1,N,1

#define N 1000010

#define read freopen("in.txt", "r", stdin)

const ll  INFll = 0x3f3f3f3f3f3f3f3fLL;

const int INF= 0x7ffffff;

const int mod =  ;

int w,n,vh;

int x[N],y[N],s[N];

int solve(int v){

    double ll=x[],rr=x[]+w;

    for(int i=;i<n;++i){

        double t=1.0*(y[i]-y[i-])/v;

        ll-=t*vh;

        rr+=t*vh;

        if(ll>1.0*(x[i]+w)||rr<1.0*x[i])return ;

        ll=max(ll,1.0*x[i]);

        rr=min(rr,1.0*x[i]+w);

    }

    return ;

}

int main()

{

    int c,len;

    scanf("%d",&c);

    while(c--){

        scanf("%d%d%d",&w,&vh,&n);

        for(int i=;i<n;++i)

            scanf("%d%d",&x[i],&y[i]);

        scanf("%d",&len);

        for(int i=;i<=len;++i)

            scanf("%d",&s[i]);

        sort(s+,s+len+);

        int l=,r=len,f=,tmp;

        while(l<=r){

            int mid=(l+r)>>;

            if(solve(s[mid])){

                tmp=mid;

                l=mid+;

                f=;

            }

            else r=mid-;

        }

        if(f)

        printf("%d\n",s[tmp]);

        else printf("IMPOSSIBLE\n");

    }

return ;

}