[BOJ] 19607 Surmising a Sprinter’s Speed

0. 들어가기

• 문제 링크 : https://www.acmicpc.net/problem/19607
• 정답 코드 : http://boj.kr/3348e60f16544857b2c9c59fcd7b6cfb

1. 문제 요약

• 동서로 난 길이 있고, 그 위에 원점(바위)이 있다.
• 위치는 원점에서 떨어진 만큼 서쪽은 음수, 동쪽은 양수로 나타낸다.
• T초에서의 Street Sprinter의 위치 X가 주어지면, Street Sprinter의 최대 속력을 구하라.

1.1. 입력

N

이후

N

줄마다

T

X

• N
  : 관측 횟수,
  2 \le N \le 100,000
• T
  : 관측된 시간,
  0 \le T \le 1,000,000,000
• X
  : 관측된 위치,
  −1,000,000,000 \le N \le 1,000,000,000

1.2. 출력

• 최대 속력(m/s)를 출력한다. 오차는
  C
  가 답일 때,
  \lvert X - C\rvert / C \lt 10^{-5}
  인
  X
  까지 허용된다.

2. 풀이 정리

• \{ T, X \}
  의 의 배열을 입력받는다.
  • cin >> arr[i].first >> arr[i].second;
• 시간(
  T
  ) 기준으로 정렬한다.
  • sort(arr.begin(), arr.end());
• 모든 인접한 구간에 대해서 속력을 구한다.
  • distance_diff = abs(arr[i].second - arr[i - 1].second);
  • time_diff = arr[i].first - arr[i - 1].first;
• 이 속력 중 최고 속력을 출력한다.
  • ans = max(ans, distance_diff / time_diff);

3. 구현

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

#define pii pair<int, int>

int N;
vector<pii> arr;
double ans = 0;

int main()
{
	cin >> N;
	arr.resize(N);

	for (int i = 0; i < N; i++)
	{
		cin >> arr[i].first >> arr[i].second;
	}

	sort(arr.begin(), arr.end());

	for (int i = 1; i < N; i++)
	{
		double distance_diff = abs(arr[i].second - arr[i - 1].second);
		double time_diff = arr[i].first - arr[i - 1].first;

		ans = max(ans, distance_diff / time_diff);
	}

	cout << ans;

	return 0;
}