Codeforces Round #365 (Div. 2) C. Chris and Road 实数级的二分法、几何

Source

Codeforces Round #365 (Div. 2)

My Solution

实数级的二分法、几何

可以把问题分成2种情况

第一种情况：车到线之前， 行人通过             //遍历 n 个点

第二种情况：车到线之后，行人通过             //即行人等了x分钟之后， 开始过马路， 刚好可以安全通过， nlogn  二分答案 + 遍历 n 个点

Y ( ^ _ ^ ) Y 实数级的二分法

最开始用的 eps = 1e-6， Wrong answer on test 3

然后改成 eps = 1e-9 就过了。

二分部分的代码

double l = 0, r = INF, x;         //!ans = 0; 才是左边界  注意左右边界

while(l + eps < r){                //

x = (l + r) / 2;

if(check(x)) r = x;

else l = x;

}

复杂度 O(nlogn)

#include 
#include 
#include 
using namespace std;
typedef long long LL;
const int maxn = 1e4 + 8;
const int INF = 1e9;
const double eps = 1e-9;

struct p{
    double x, y, time;
} val[maxn];

int n;
double w, v, u, x, y;

inline bool check(double time)
{
    for(int i = 0; i  < n; i++){
        if((val[i].y / u + time - val[i].time) < eps){ return false; } } return true; } int main() { #ifdef LOCAL freopen("a.txt", "r", stdin); //freopen("b.txt", "w", stdout); int T = 1; while(T--){ #endif // LOCAL ios::sync_with_stdio(false); cin.tie(0); bool flag = true; cin >> n >> w >> v >> u;
    for(int i = 0; i < n; i++){ cin >> x >> y;
        val[i].x = x;
        val[i].y = y;
        val[i].time = x / v;
    }

    for(int i = 0; i < n; i++){ if((val[i].y / u - val[i].time) > eps){
            flag = false;
        }
    }

    if(flag){
        cout << fixed << setprecision(10) <<  w / u <<endl;
    }
    else{
        double l = 0, r = INF, x;         //!ans = 0; 才是左边界  注意左右边界
        while(l + eps < r){                //!!!!!!  不是 l < r, 这里 l == r 达不到的
            x = (l + r) / 2;
            if(check(x)) r = x;
            else l = x;

        }
        cout << fixed << setprecision(10) << x + w / u << endl;
    }


    #ifdef LOCAL
    cout << endl;
    }
    #endif // LOCAL
    return 0;
}

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx