[14488] 준오는 급식충이야!

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

처음에

모든 친구들에 대해서 만족하는 점을 찾으면 되겠다고 생각했습니다.

그래서 이분탐색으로 접근을 했습니다.

하지만 1차원 선상에서 소수(double)에서도 모일 수 있으므로

이분탐색을 사용하기가 애매했습니다.

그래서 다시 생각했는데 

구현하는 것이 정말 단순했습니다.

그냥 N의 시간으로 가면서 모든 학생들이 모일 수 있는 포인트로 좁혀가다가

그 포인트에 벗어나는 학생이 있으면 홍수에 당하는 것이고 아니라면 만날 수 있는 것이라고 생각했습니다.

minPos와 maxPos가 모든 학생들이 접근할 수 있는 범위입니다.

for문안에서 left와 right는 시간 * 속력으로 이동할 수 있는 거리를 구하여 현재 위치에서 더하고 빼서 

움직일 수 있는 범위를 나타냅니다.

첫번째 if문이 있는 경우가 아니라면 모일 수 있는 것입니다.

풀코드입니다.

#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
 
#define ll long long
#define MOD ((int)1e9 + 9)
#define MAX_SIZE (int)1e5
#define mp make_pair
#define INF 987654321
#define pii pair<int, int>
 
pii v[(int)5e5];
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
 
    int n;
    double t;
 
    cin >> n >> t;
 
    for (int i = 0; i < n; i++) {
        cin >> v[i].first ;
    }
 
    for (int i = 0; i < n; i++) {
        cin >> v[i].second;
    }
 
    double minPos = 0, maxPos = INF;
 
    for (int i = 0; i < n; i++) {
        double left = v[i].first - v[i].second * t;
        double right = v[i].first + v[i].second * t;
 
        if (maxPos < left || right < minPos) {
            puts("0");
            return 0;
        }
        
        maxPos = min(maxPos, right);
        minPos = max(minPos, left);
    }
 
    puts("1");
 
    return 0;
}