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

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

N=50000명의 학생이 시간 T 안에 전부 만날 수 있나를 확인해야하는데, 2중 for문을 돌면서 두 학생이 만나는 시간(= abs(x[i]-x[j]) / (v[i]+v[j]))이 T보다 큰지를 확인한다면 답을 알 수는 있지만 시간초과가 발생합니다.

대신 관점을 달리하여 각 학생이 시간 T 안에 도달할 수 있는 영역을 저장해두고 이를 갱신하면서 각 학생에 대해 영역과 겹치는 부분이 있는지를 확인하면 됩니다. 이러면 O(N)으로 풀 수 있습니다.

그런데 문제가 있는데, T를 실수로 저장하면 실수 오차 때문에 답이 틀릴 수 있습니다.(이 실수오차로 인해 재채점에서 나가리됐습니다.) 이를 방지하려고 T를 10000배해서 들고있으면 long long 범위를 넘어갈 수 있습니다.

C나 C++로 구현을 하려고 한다면 Big Integer를 처리할 수 있는 구조체를 만들어서 풀어야하고, 사실 그보다는 python으로 푸는 것이 깔끔합니다.

https://github.com/encrypted-def/BOJ/blob/master/14488.py