top of page

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;
}

Recent Posts

See All

CCC '24 J5 - Harvest Waterloo

#include<iostream> #include <vector> #include <algorithm> #include <cmath> #include <stack> using namespace std; int main() { int r, c, sr, sc; cin >> r; cin >> c; int p[r][c]; bool v

CCC '24 J4 - Troublesome Keys

#include <iostream> #include <string> #include <map> #include <vector> #include <algorithm> #include <cmath> using namespace std; int main() { string ps; string ds; cin >> ps; cin >> ds;

CCC '22 J5 - Square Pool

#include<iostream> #include <vector> #include <algorithm> #include <cmath> using namespace std; bool rowcom(pair<int, int> a, pair<int, int> b){ return a.first < b.first; } bool colcom(pair<int,

Σχόλια


bottom of page