Three Transmitters
National Olympiad — National round (2011 season)
Submission name: radars.cpp
Problem summary
Cities lie on a line at given coordinates. Choose three with coordinates a < b < c to maximize (c − b)(b − a). Find the maximum transmission power.
Input
n followed by n integer coordinates in arbitrary order.
Output
The largest possible product of adjacent distances.
Constraints
3 ≤ n ≤ 100,000; −1,000,000 ≤ coordinate ≤ 1,000,000.
Worked example
An independently prepared example for this explanation.
Input
5 3 1 5 2 4
Output
4
Solution analysis
- Fix the middle coordinate b. Moving the left transmitter farther left can only increase b − a, and moving the right transmitter farther right can only increase c − b. Thus an optimal choice uses the global minimum and maximum coordinates as endpoints.
- Find those extrema, then try every supplied city as the middle. Compute each product with 64-bit integers and keep the greatest.
- For coordinates 1 through 5, choose endpoints 1 and 5. The middle candidates 2, 3, and 4 give products 3, 4, and 3; the best is 4 at coordinate 3.
Why it works
For any valid triple, replacing its endpoints with the global minimum and maximum preserves the middle city and cannot decrease either nonnegative distance. Hence some optimal triple uses these endpoints. The scan evaluates every possible middle city for them, so its maximum is globally optimal.
Watch out. Coordinates need not be sorted. Multiply in 64 bits: products may reach 10^12. Repeated coordinates add no new positive-distance choices; an instance without three distinct coordinates has no strict triple.
Commented C++17 solution
An independently written complete program with standard headers.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int n;
cin >> n;
vector<long long> coordinates(n);
for (long long &coordinate : coordinates) {
cin >> coordinate;
}
long long left = *min_element(coordinates.begin(), coordinates.end());
long long right = *max_element(coordinates.begin(), coordinates.end());
long long best = 0;
// For each middle city, the extreme endpoints maximize both distances.
for (long long middle : coordinates) {
best = max(best, (middle - left) * (right - middle));
}
cout << best << '\n';
}