Table Of Contents
0. 들어가기
1. 문제 요약
- 동서로 난 길이 있고, 그 위에 원점(바위)이 있다.
- 위치는 원점에서 떨어진 만큼 서쪽은 음수, 동쪽은 양수로 나타낸다.
- T초에서의 Street Sprinter의 위치 X가 주어지면, Street Sprinter의 최대 속력을 구하라.
1.1. 입력
이후 줄마다
- : 관측 횟수,
- : 관측된 시간,
0 \le T \le 1,000,000,000
- : 관측된 위치,
−1,000,000,000 \le N \le 1,000,000,000
1.2. 출력
- 최대 속력(m/s)를 출력한다. 오차는 가 답일 때,
\lvert X - C\rvert / C \lt 10^{-5}
인 까지 허용된다.
2. 풀이 정리
- 의 의 배열을 입력받는다.
cin >> arr[i].first >> arr[i].second;
- 시간() 기준으로 정렬한다.
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;
}