CCC 2020 S1: Surmising a Sprinter's Speed

Sort the points by time. Then loop through consecutive pairs to find the constant speed over each interval. The answer is the maximum of the speeds.

Time complexity:O(NlogN).

#include <iostream>

#include <utility>

#include <algorithm>

#include <iomanip>

using namespace std;

pair<double, double> A[100002];

int n;

double res = 0;

int main(){

	cin>>n;

	for(int i = 0; i < n; i++)

		cin>>A[i].first>>A[i].second;

	sort(A, A+n);

	for(int i = 1; i < n; i++){

		res = max(res, abs(A[i].second-A[i-1].second)/(A[i].first-A[i-1].first));

	}

	cout<<fixed<<setprecision(10)<<res;

	return 0;

}