BOJ 14488

백준 14488, Math

$\frac{ |x^*- x_i| }{ v_i } \leq T \forall i \in [1 \cdots N]$
을 만족하는지 구하면 된다. 식이 어려워 보여 그렇지,
$|x^* - x_i| \leq Tv_i$

$x^* \leq x_i + Tv_i$ 와 $x^* \geq x_i - Tv_i$
를 동시에 만족하는지 본다.
$s_i = x_i - Tv_i, e_i = x_i + Tv_i$
로 모든 $[s_i, y_i]$ 구간을 겹쳤을 때 남는 구간이 있는지 확인하면 된다.

하나 조심 할 것은, floating point precision 문제 때문에
그냥 double 을 쓰면 WA가 나오고, long double을 써야 AC가 나온다.

오랜만에 한 번에 맞춘 문제라서, 다시 복귀한 기분이 든다.

Source Code

14488링크

// https://www.acmicpc.net/problem/14488

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>

using namespace std;

#define ll long long

#define pii pair<int, int>
#define pll pair<ll, ll>
#define MAXI 1000000000
#define cplx complex<double>
#define MOD 9901
const double PI = acos(-1);
const ll INF = INT_MAX / 4;

//double 로는 precision 모자라서 WA. use long double.
long double eps = 1e-8;
int N;
ll X[50050];
ll V[50050];
long double T;

#define pdouble pair<long double,long double>

pdouble get_range(ll x, ll v){
    long double s, e;
    e = x * 1.0 + T * v;
    s = x * 1.0 - T * v;
    s = (s < 0.0 ? 0.0 : s);
    return pdouble(s,e);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> N;
    cin >> T;
    for (int i = 0; i < N;++i)
        cin >> X[i];
    for (int i = 0; i < N;++i)
        cin >> V[i];

    pdouble init_range = get_range(X[0], V[0]);

    for (int i = 1; i < N;++i){
        pdouble range_i = get_range(X[i], V[i]);
        init_range.first = (range_i.first > init_range.first) ? range_i.first : init_range.first;
        init_range.second = (range_i.second < init_range.second) ? range_i.second : init_range.second;
    }

    int ans = (init_range.second >= init_range.first) ? 1 : 0;
    printf("%d", ans);

    return 0;
}

/*

//ntopia's solution.
#include <algorithm>
#include <iostream>
using namespace std;

int n;
double t;
int pos[50000], vel[50000];

void proc() {
    cin >> n >> t;
    for (int i = 0; i < n; ++i) {
        cin >> pos[i];
    }
    for (int i = 0; i < n; ++i) {
        cin >> vel[i];
    }
    double mn = -1e+20, mx = 1e+20;
    for (int i = 0; i < n; ++i) {
        double left = pos[i] - vel[i] * t;
        double right = pos[i] + vel[i] * t;
        mn = max(mn, left);
        mx = min(mx, right);
    }
    cout << (mn <= mx + 1e-7) ? 1 : 0;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    proc();
    return 0;
}

*/

PREVIOUSBOJ 1011

NEXTBOJ 23255