https://www.codechef.com/MACE2021/problems/MCODE10

varghesebabu · February 7, 2021, 6:54am

DIFFICULTY : HARD

PREREQUISITES:

Geometry, Binary Search

PROBLEM:

Mr. Veer Pratap is a spy of country I. He is tasked to infiltrate the illegal camp of a Terrorist group which is in deep into the mountains.The only way there is through the mountain tops and assume that all the mountain paths towards the goal can be represented in a plain of x, y(ie, can be represented in a polyline). The defense system of the terrorist camp has a height ‘H’ and is at a position (xk, yk) is set to detect anything around it unless its vision is blocked by any mountain peaks ie, if a straight line can be drawn to the terrain without any intersection(and assuming the persons height is negligible). He is given the points of terrain change ie, places of transition of slopes and the point of location of the defense mechanism. Help him to find the distance where he has to put his guard high so as to not be detected by the terrorist defense system.

EXPLANATION:

Let’s start with the general idea of the solution. To solve the problem, we need to iterate over all relief segments and understand, which part the mountain range is seen by the defense tower. A mountain range point can be hidden from the defense tower by several mountains, but it is enough to track only the highest mountain. Generally speaking, the relief segments can be processed in any order, bit it would be more convenient to iterate on them backwards — i.e. in the order from the defense tower to the start point. Processing the segments in reversed order will allow to recalculate the highest mountain easier.

Let’s now discuss implementation details. Formally speaking, there are n
relief points pi=(xi,yi) (1≤i≤n) and the defense tower point E=(xn,yn+H). Each relief point defines its own angle αi, which is measured counter-clockwise between positive direction of the OX axis and the (E,pi) vector. Now, having two relief points pi and pj (i<j), it can be said that pi is hidden from the defense tower if αi>αj. When this check is implemented in the solution, to avoid the precision loss, it is recommended to use vector product and analyse its sign to understand the relation of the angles. This check is done in O(1)time.

Being able to understand when a point is hidden from the defense tower by another point, it is possible to calculate, which part of a mountain range(pi,pi+1)is seen by the defense tower. First of all let’s note, that if the mountain rangeleft point pi is hidden by its right point pi+1, then the entire mountain rangeis hidden from the defense tower. Now, we have the situation when left mountain rangepoint is not hidden from the defense tower by its right point. But the mountain rangeor its part can still be hidden by the highest mountain (point M), which is a point with minimal angle from all relief points, located to the right of our segment. Here three cases are possible:

both pi and pi+1 are hidden by M in this case the entire mountain rangeis hidden and we switch to the next segment;

both pi and pi+1 are visible by the defense tower (not hidden by the highest mountain M) — in this case the entire mountain rangeis visible and we should add its length to the answer;

left mountain rangepoint pi is visible by the defense tower, but right mountain rangepoint pi+1 is hidden by M — in this case we need to find intersection point I of the mountain range(pi,pi+1) and the ray (E,M). What is left - add length of (pi,I) mountain range to the answer.

It is very convenient to implement mountain range and ray intersection in a parametric way, when intersection point I is represented as I=pi+t1∗(pi+1−pi)=E+t2∗(M−E) and then parameters t1 and t2 are found as solutions of linear equation system.

Now, let’s conclude the final algorithm:

Iterate over all relief segments from right to left, keeping the highest mountain point M

Analyze how left and right points of the current mountain rangeare located relatively to each other and point M

Recalculate M taking points of the current segments as candidates for the highest mountain.

Total algorithm complexity is O(N).

SOLUTIONS:

Setter's Solution

#define _USE_MATH_DEFINES
#include
#include
using namespace std;
int N,H;
int x[2<<17],y[2<<17];
long long cross(int i,int j)
{
long long xi=x[i]-x[N-1];
long long yi=y[i]-y[N-1]-H;
long long xj=x[j]-x[N-1];
long long yj=y[j]-y[N-1]-H;
return xiyj-xjyi;
}
main()
{
scanf(“%d%d”,&N,&H);
for(int i=0;i<N;i++)
{
scanf(“%d%d”,&x[i],&y[i]);
}
int mn=N-1;
double ans=0;
for(int i=N-2;i>=0;i–)
{
long long t=cross(mn,i);
if(t==0)
{
if(mn==i+1)
{
ans+=hypot(x[i]-x[i+1],y[i]-y[i+1]);
}
mn=i;
}
else if(t<0)
{
double theta=atan2(y[N-1]+H-y[mn],x[N-1]-x[mn])-atan2(y[N-1]+H-y[i],x[N-1]-x[i]);
double l=hypot(y[N-1]+H-y[i],x[N-1]-x[i]);
double alpha=atan2(y[N-1]+H-y[i],x[N-1]-x[i])-atan2(y[i+1]-y[i],x[i+1]-x[i]);
ans+=l*sin(theta)/sin(theta+alpha);
mn=i;
}
}
printf(“%.4lf\n”,ans);
}

Tester's Solution

Same Person

Editorialist's Solution