题解：P9314 [EGOI 2021] Railway / 瑞士铁路

· · 题解

一篇用 double 的做法

分析题面

### 判断是否在隧道 首先我们需要得知两车相遇位置，由于隧道具有单调性（因为互不重叠），所以可以二分求出相遇位置是否在隧道。 下面是求 $i$，$j$ 两车相遇位置 $met$ 的方法： - 后出发的出发后两车共走路程 $dis=s+c_{i}+d{j}-2 \times\max\{c_{i},d_{j}\}

此时二分三个区间①②③（二为隧道）。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=200010;
int s,t,m,n,x[N],y[N],a[N],b[N];

bool work(int i,int j){
    int l=1,r=t,mid;
    double met=(s+b[j]-a[i])/2.0;
    while(l<=r){
        mid=(l+r)>>1;
        if(x[mid]<met&&met<y[mid]) return 1;
        if(y[mid]<=met) l=mid+1;
        else r=mid-1;
    }
    return 0;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>s>>t>>m>>n;
    for(int i=1;i<=t;i++) cin>>x[i];
    for(int i=1;i<=t;i++) cin>>y[i];
    for(int i=1;i<=m;i++) cin>>a[i];
    for(int i=1;i<=n;i++) cin>>b[i];
    for(int i=1;i<=m;i++){
        for(int j=1;j<=n;j++){
            if(work(i,j)){
                cout<<"YES";
                return 0;
            }
        }
    }
    cout<<"NO";
    return 0;
}