PROBLEM LINK:
Author: Amit Kumar Ray
Testers: Pankaj Mandrawal
Editorialist: Jatin Khandual
DIFFICULTY:
EASY
PREREQUISITES:
Observations, Basic Math, Ternary Search
PROBLEM:
Given two points P and Q in the coordinate-plane, you need to find a point R on the x-axis that minimizes the overall distance \overline{\rm PR}+\overline{\rm RQ}. Print this optimal distance.
QUICK EXPLANATION:
The point R can be ternary-searched in the interval [0, 1e9]. Alternatively, for two points P(x_1, y_1) and Q(x_2, y_2), the optimal distance is equivalent to \overline{\rm P'Q} where P'(x_1, -y_1) is the reflection of P across the x-axis.
EXPLANATION:
It is not difficult to see that the distances \overline{\rm PR}+\overline{\rm RQ} for all R whose x-coordinate lies in the range [0, 1e9] follows a parabolic curve (i.e. it is unimodal) in that it first decreases to reach a minimum and then increase again. The point where the curve attains its minimum can be found with ternary search under the given time-limit.
Note: It takes about 200-300 iterations (independent of the interval limits) per test case to achieve a precision of about 10^{-6}.
ALTERNATE EXPLANATION:
Alternatively, for two points P(x_1, y_1) and Q(x_2, y_2), the optimal distance is equivalent to \overline{\rm P'Q} where P'(x_1, -y_1) is the reflection of P across the x-axis.
SOLUTIONS:
Setter's Solution
//“Make it work, make it right, make it fast.” – Kent Beck
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double dd;
const int siz = 1e6 + 5;
const int MOD = 1e9 + 7;
#define endl '\n'
#define deb(x) cout << #x << " = " << x << endl;
void solve(){
long double x, y, X, Y;
cin >> x >> y >> X >> Y;
assert(x >= 0 and x <= 1e9);
assert(y >= 0 and y <= 1e9);
assert(X >= 0 and X <= 1e9);
assert(Y >= 0 and Y <= 1e9);
long double ans = 0;
Y = -Y;
ans = sqrtl(((X-x)*(X-x)) + ((Y-y)*(Y-y)));
cout << fixed << setprecision(7) << ans << endl;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t = 1;
cin >> t;
assert(t >= 1 and t <= 1e5);
while(t--){
//tt++;
//cout << "Case #" << tt << ": ";
solve();
}
return 0;
}
Editorialist's Solution
//author: hitch_hiker42;
#include<bits/stdc++.h>
using namespace std;
//solution:
void hike() {
int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;
double lo = 0, hi = 1e9;
auto f = [&](double m) {
return hypot(x1 - m, y1) + hypot(x2 - m, y2);
};
while(hi - lo > 1e-6) {
double mid1 = lo + (hi - lo) / 3;
double mid2 = hi - (hi - lo) / 3;
double f1 = f(mid1), f2 = f(mid2);
if(f1 < f2) hi = mid2;
else lo = mid1;
}
cout << fixed << setprecision(7) << f(lo) << "\n";
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
int t; cin >> t;
while(t--) hike();
return 0;
} //farewell, until we meet again..