A life guard is sitting on a beach on a lookout for potential emergencies. He suddenly notices a person who is drowning and springs to action. He runs up to the sea with a speed f*V km/hr, then he swims straight to the person at the rate V km/hr (both in straight lines and where f is a multiplying factor as humans run much faster than they can swim). He wants to minimize the time taken to get to that person.
Since the lifeguard runs faster, it will save some more time to run a longer distance rather than going straight and thus swimming a long distance. However, this comes with the trade-off that running longer can actually mean going a longer distance thus taking more time.
Thus, it can be logically inferred that, there must exist a spot on the Beach- Sea Interface where, if the lifeguard directly runs to from his starting location, and then swims directly to the drowning person, it’ll take the least
time.
Given the starting location , the location of the drowning person and the multiplying factor f, find the optimized spot for fastest time.
Assumptions/Problem Explanation:
- Consider that everything is in a two dimensional (2D) plane. The x axis represents the Beach-Sea interface, positive Y axis is towards land and negative Y-axis towards sea (See image above).
- The Y-axis along with origin is at some arbitrary location to the left ofboth the lifeguard and the drowning person. Since the origin point remains the same for both of them and the staring locations are given relative to
the origin , its actual location does not matter. The only thing to note is, the origin and Y axis is to the left of both of them, so beach is always in 1st quadrant and sea in 4th. Thus, the positions of lifeguard and the
drowning person are given as their (x,y) co-ordinates. (7,5) means the person is 7 units on the axis and 5 units on the positive y axis, and hence on the beach. Similarly, (7,-5) means the person is 7 units on the axis and 5 units on the negative Y axis, and hence in sea. - The lifeguard both runs and swims in perfectly straight lines.
- With regards to everything explained above, your task is to find a point on the Beach-Sea Interface (X -axis) (x_optimized,0) to where if the lifeguard runs directly from his starting position and then swims directly from the point to the drowning person, it’ll take the least amount of time.
- All calculations must be done upto 6 decimal points accuracy and the output must be upto 6 decimal points as well.
Input Format
The input shall consist of 3 parameters :
- Starting position of the lifeguard in terms of his coordinates (x_l,y_l).
- Position of the drowning person (x_w,y_w)
- The multiplying factor f.
These parameters would be given in the following order in 5 different
lines:
x_l
y_l
x_w
y_w
f
Output Format
Output must be a single number, x_optimized, as described above. The output must be having accuracy to 6 decimal places. That is, 1 should be represented as 1.000000
Constraints
0 <= x_l < 100 (Integer)
0 <= y_l < 100 (Integer)
0 <= x_w < 100 (Integer)
-500 < y_w < 0 (Integer)
1 < f <= 15 (Integer)
Sample Input and Output
Example 1
Input
1
1
1
-1
1.2
Output
1.000000
CODE
import math
x1 = int(input())
y1 = int(input())
x2 = int(input())
y2 = int(input())
f = float(input())
if y1+y2 == 0:
a = x1*f
a = int(a)
print("{0 : .6f}".format(a))
Above code is contributed by one of our user Sai.
If you know any better approach please comment it below.
Code isn’t working ,also there maybe cases where (y1+y2)!=0, so how do we get optimized x coordinate?
Code is wrong
follow this article to get it
https://www.geeksforgeeks.org/check-if-it-is-possible-to-reach-to-the-index-with-value-k-when-start-index-is-given/
Sorry this one
https://www.geeksforgeeks.org/number-of-ways-to-reach-m-n-in-a-matrix-starting-from-the-origin-without-visiting-x-y/
import math
x1,y1,x2,y2,f=map(int,input().split())
lst=[]
if x1>=x2:
mx=x1
else:
mx=x2
for i in range(mx+1):
z=(((math.sqrt((x1-i)**2+y1**2))/f)+(math.sqrt((i-x2)**2+y2**2)))
lst.append(z)
print(‘%.6f’%lst.index(min(lst)))
output:-
5 5 5 -5 5
5.000000
Can you please explain the logic??
If you choose all int point on x axis between the guard and drowing person,and calculate time taken to travel total distance through that point,the one giving min time is our solution,..however if you want to minimize the code execution time and take float points on x axis under consideration as well use binary search logic.
//brute force solution is :
#include
#include
using namespace std;
long double xl, yl, xw, yw, f;
long double calculate_it(long double i)
{
return sqrt(((xl – i) * (xl – i)) + (yl * yl)) / f + sqrt((xw – i) * (xw – i) + yw * yw);
}
long double find_it(long double start, long double end)
{
long double i, mini, ans, count, prev = 0;
mini = 10000000000;
ans = i = start;
for (i = start; i <= end; i += 0.000001)
{
count = calculate_it(i);
if (count > xl >> yl >> xw >> yw >> f;
long double count;
if (xl > xw)
{
count = find_it(xw, xl);
}
else
{
count = find_it(xl, xw);
}
printf(“%.6lf”, (double)count);
return 0;
}
/*
Explanation :
the solution is very straight forward
In this solution we find the minimum time by calculating every single point started from x_l to x_w and the result is the point where time is minimum.
we will increase the point by 0.000001 each time because we need answer acurate up to 6 decimal point .
/*
//Efficient solution :
/*
if we observer and draw the pattern of result then we can find that the curve is
first decreasing and then increasing and their is only one minima between x_l to x_w . so we can find our x_min using binary search instead of looping through all points.
*/
// source code:
#include
#include
using namespace std;
long double xl, yl, xw, yw, f;
long double find_it(long double start, long double end)
{
long double i, mini, ans, count, prev = 0;
mini = 10000000000;
ans = i = start;
for (i = start; i <= end; i += 0.000001)
{
count = sqrt(((xl – i) * (xl – i)) + (yl * yl)) + sqrt((xw – i) * (xw – i) + yw * yw);
if (count current && next > current)
{
ans = mid;
break;
}
else if (prev > current)
{
start = mid + 0.000001;
}
else
{
end = mid – 0.000001;
}
}
return ans;
}
int main()
{
cin >> xl >> yl >> xw >> yw >> f;
long double count;
if (xl > xw)
{
count = search_it(xw, xl);
}
else
{
count = search_it(xl, xw);
}
printf(“%.6lf”, (double)count);
return 0;
}
/*
Explanation
(time)
^
| * *
| * *
| * *
| * *
| * (position)
| |
(x_l) (x_w)
|___________________________|
(x_min is between this point)
we can use binary search by using the following condition :
0) start = min(x_l,x_w) , end = min(x_l,x_w)
1) calculate middle = (start + end )/2
2) find the time taken for position (middle-0.000001) , (middle) ,(middle + 0.000001) by using the formula ;
3) let the calculated time be prev, current and next respectively.
we can find direct our binary search using following condition ;
if( time taken in middle position is smaller than both prev and next )
then this is the required position
else if( time taken in middle position is >time taken n prev postion )
then move right
else
move left
*/
#include
#include
using namespace std;
long double xl, yl, xw, yw, f;
long double find_it(long double start, long double end)
{
long double i, mini, ans, count, prev = 0;
mini = 10000000000;
ans = i = start;
for (i = start; i <= end; i += 0.000001)
{
count = sqrt(((xl – i) * (xl – i)) + (yl * yl)) + sqrt((xw – i) * (xw – i) + yw * yw);
if (count current && next > current)
{
ans = mid;
break;
}
else if (prev > current)
{
start = mid + 0.000001;
}
else
{
end = mid – 0.000001;
}
}
return ans;
}
int main()
{
cin >> xl >> yl >> xw >> yw >> f;
long double count;
if (xl > xw)
{
count = search_it(xw, xl);
}
else
{
count = search_it(xl, xw);
}
printf(“%.6lf”, (double)count);
return 0;
}
#include
#include
using namespace std;
long double xl, yl, xw, yw, f;
long double calculate_it(long double i)
{
return sqrt(((xl – i) * (xl – i)) + (yl * yl)) / f + sqrt((xw – i) * (xw – i) + yw * yw);
}
long double search_it(long double start, long double end)
{
long double mid, current, prev, next;
long double ans = -1;
while (true)
{
mid = (start + end) / 2;
prev = calculate_it(mid – 0.000001);
current = calculate_it(mid);
next = calculate_it(mid + 0.000001);
if (prev > current && next > current)
{
ans = mid;
break;
}
else if (prev > current)
{
start = mid + 0.000001;
}
else
{
end = mid – 0.000001;
}
}
return ans;
}
int main()
{
cin >> xl >> yl >> xw >> yw >> f;
long double count;
if (xl > xw)
{
count = search_it(xw, xl);
}
else
{
count = search_it(xl, xw);
}
printf(“%.6lf”, (double)count);
return 0;
}
#include <iostream>
#include <cmath>
using namespace std;
long double xl, yl, xw, yw, f;
long double calculate_it(long double i)
{
return sqrt(((xl – i) * (xl – i)) + (yl * yl)) / f + sqrt((xw – i) * (xw – i) + yw * yw);
}
long double search_it(long double start, long double end)
{
long double mid, current, prev, next;
long double ans = -1;
while (true)
{
mid = (start + end) / 2;
prev = calculate_it(mid – 0.000001);
current = calculate_it(mid);
next = calculate_it(mid + 0.000001);
if (prev > current && next > current)
{
ans = mid;
break;
}
else if (prev > current)
{
start = mid + 0.000001;
}
else
{
end = mid – 0.000001;
}
}
return ans;
}
int main()
{
cin >> xl >> yl >> xw >> yw >> f;
long double count;
if (xl > xw)
{
count = search_it(xw, xl);
}
else
{
count = search_it(xl, xw);
}
printf(“%.6lf”, (double)count);
return 0;
}
Accepted Solution in c
#include
#include
int main(){
int x1,y1,x2,y2,f;
float d;
scanf(“%d”,&x1);
scanf(“%d”,&y1);
scanf(“%d”,&x2);
scanf(“%d”,&y2);
scanf(“%d”,&f);
//phusics formula to calculate distance
f=sqrt(((y1*y1*(y2*y2+x2*x2)/f*f*y2*y2))-(y1*y1));
printf(“%0.6f”,f);//to get precision of 6
}
import java.util.*;
import java.text.DecimalFormat;
class Main
{
public static void main(String[] args)
{
Scanner in=new Scanner(System.in);
double xl=in.nextDouble();
double yl=in.nextDouble();
double xw=in.nextDouble();
double yw=in.nextDouble();
double f=in.nextDouble();
DecimalFormat deci=new DecimalFormat(“0.000000”);
double xopt=((f*yl*xw)-(xl*yw))/(f*yl-yw);
System.out.println(deci.format(xopt));
}
}