KGP16B- Editorial

general
, , , , ,
1

PROBLEM LINK:

[Contest][1]
[Practice][2]

Setter-
Tester- Multiple
Editorialist- [Abhishek Pandey][3]

DIFFICULTY:

Medium

PRE-REQUISITES:

Geometry, [Point Inside a Polygon Algorithms][4] , Distance formula, Math, Conditionals.

Knowing about vectors and cross product will help in understanding Point inside a Polygon algorithms, and is hence advised.

DO NOT USE THE ALGORITHM GIVEN AT GEEKS FOR GEEKS FOR POINT INSIDE POLYGON- ITS INCORRECT AND FAILS AT EDGE CASES!!

PROBLEM:

You are asked to find the shortest distance between 2 points such that it does not cross the given quadrilateral. In case no answer exists, print -1.

QUICK EXPLANATION:

We first find out if an answer is possible or not by using Point inside a polygon algorithms, such as Crossing Number and Winding Number (refer to the link in pre-requisites). Once we know an answer is possible, its all about conditionals. Alternatively, we can use dp to ease out and avoid those tedious cases!

EXPLANATION:

Depending on your approach and carefulness in implementation, this problem can either by an easy point or spawn of the devil itself. Usually, when such kind of questions are faced, its better to sit back and think first. Think on what tools or functions you might need, what operations you would be performing. Like, we will be calculating distances between points a LOT in this problem. It isnt advised to write the formula everywhere you use that. You have more chances of committing error that way. Make a clean function of it, and use it whenever you need. These type of questions dont take long to get really messy if you dont follow proper programming approach and practice.

Now, coming to the question, we can clearly see that the answer will either exist or be -1. ("Great revelation you made @vijju123 "- lol). Coming to the editorial, it is divided into 2 sections, one for each part. :slight_smile:

When no answer exist-

This clearly happens when one of them is inside the castle, while other is outside it. This is also one of the easier - but trickier section to code.

Now, finding if a point is inside a polygon or not, is a standard question, with well known algorithms. There are 2 tools to determine if a point is inside a polygon or not- Winding Number and Crossing Number. You can read about them in the link given- its no use doing repetitions in an editorial.

Now, I’d suggest to always use winding number, because of 2 cases-

  • Crossing Number has some corner cases. Say your horizontal line crosses polygon at edge. Its intersection is counted twice instead of once, since each vertex is a part of 2 edges. (So if we dont handle this manually, we will add 2 to answer instead of 1). Lets say you handled this case, then theres another case where both points are outside, and the line joining them just touches a vertex. Another case too handle :slight_smile: . So on and so forth you can find ample of problems in this approach.
  • Crossing number holds no good if polygon is twisted, i.e. edges intersect with each other. Winding number works there.

Winding number’s implementation can be seen in the link, and in the editorialist’s solution.

For those who want to use crossing number, there are 2 ways to relieve yourself of these case handling.

One is, you find out point of intersection. In crossing number, we see intersection of the horizontal ray (from point to be tested) with edges. We know equation of both lines. We also know the y co-ordinate, since ray is horizontal and we know the point to be tested. Find out the x co-ordinate now. See if this intersection happens on edge or not. Make sure you count each point only once. HORIZONTAL EDGES MUST BE EXEMPTED FROM CROSSING NUMBER TEST!

Another one used by testers is highly innovative and impressive. What they did, is that instead of taking a strict horizontal ray, they took an “Almost horizontal ray”. i.e., the ray starts from P , say (x,y) and ends at (x+{10}^{6},y+1). This ray, cannot be collinear with any point of the input, due to constraint of point being integers and extremely low slope of this ray. But the line intersection part is unaffected by it. This gets rid of all those corner cases like - line touching vertex, line intersecting vertex etc.

When answer exists-

Now, this part is pretty straight-forward, but really straining. There are two ways to approach this part.

The standard solution is of course, making cases. You can make cases on these lines-

  1. When Jared can go straight to Payton
  2. When Jared has to move across 1 vertex to go to payton. (Goto Vertex A and from there to Payton)
  3. When Jared has to move across 2 vertices (From his original position to Vertex A and from there to Vertex B and from there to Payton).
  4. When Jared has to move across 3 vertices.

Case 1 and 2 are pretty easy.

In case 3, you need to make sure of order, and if he can go to diagonally opposite vertex in straight path or not (This is done by checking if Jared and mid point [or any point] of this diagonal, both lie completely inside or completely outside). Further, you must check for direction. Meaning, if he visits vertex 1, he can either goto vertex 2 and then to payton, or goto vertex 4 and then to payton. Dont miss these cases!

Case 4 is by far quite complex. Since we are visiting 3 vertices, you can prove that you dont need to check for diagonals (visiting 3rd vertex will be, else, redundant). Just take care of order. That is, check for both paths (Jared,1,2,3,Payton) and (Jared,1,4,3,payton).

This was the first approach. Another approach used by tester, which is quite elegant, is to use dynamic programming.

First he took all 6 points in an array. The points were as - (Jared, 4 points of quadrilateral, Payton)

Then he made a 2-D array $d

p

[

6

]

[

6

]$ , where $d

p

[

i

]

[

j

]$ represents “Shortest distance from i to j”. First, he calculated the distance between adjacent edges (i.e. $dp

[

i

]

[

i

%4

+1]$). Then he checked if its possible to visit diagonally opposite vertex or not. $dp[i][i]$ is, as usual, 0. Once this was done, he looped through all 6 points **(Jared, 4 points of quadrilateral, Payton)** as- for all points from i=0 to 6: for all points from j=i+1 to 6 if(either point i or point j are Jared or Payton) bool canGoStraight=true; for all k=points of polygon if point i,j,k and (k+1)%4 are all distinct, and line between i and j intersects edge between k and (k+1)%4 canGoStraight=false; if(canGoStraight==true) dp[i][j]=d[j][i]=Straight distance b/w i and j; Now the only thing left is to see for cases where its not possible to go straight, i.e. we must visit at least one intermediate point/vertex to goto Payton. He took care of it as- for(int k=0;k<6;k++) { //Let k be the intermediate point. for(i=0;i<6;i++) { for(j=0;j<6;j++) { dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]); //If no straight path from i to j exists, then considering if we can //visit any intermediate point k to reach there. } } } Be careful though! The outer-most loop $must$ be that of k! If it is not, then you wont compute dp table properly. In this implementation, you are checking all points, as in, whether its possible to move from this vertex to another in shorter way, or of jared moving to vertex i in a shorter way etc. Obviously, its performing more than, say 200 operations to determine final answer. If k is not the outermost loop, say you made it the innermost loop, then after mere 30 iterations you will come to condition- for(i=0;i<6;i++) for(j=0;j<6;j++) //j is now 5. But point 0 and point 5 are Jared and Payton- you are calculating the answer first and then updating the dp table correctly, which obviously leads to wrong answer! ### SOLUTION: [Solution 1 -Based on dp approach of tester][6] [Solution 2- Based on Conditionals][7] - Refer to implementation of winding number, and crossing number here. ### Chef Vijju's Corner :D 1.Some people feel that geometry problems are really tough. YES THEY ARE SOO RIGHT!! (Lol joke). But honestly, on a serious note, geometry problems need a good programming habit. You have almost infinite corner cases. You need to know the theorems, and you will have to write functions- because performing those mundane operations like finding distance between 2 points repeatedly is tedious. Again, not all are tough in implementing, but all have one edge case or the other. 2.How would you extend this problem for $N-sided$ $Polygon$? I think the tester's code can be modified a bit to give answer for this, because making conditionals gets exponentially tedious as number of vertices increase. Can you come up with the solution for this? 3.The tester (i.e @errichto i.e [Kamil][8] ) did this question in mere 90 lines!! Though I should not say 90, since many of the statements were clumped together in 1 line and some parts of the code were messy. Also, it had almost nil comments for the poor editorialist who has to understand what he did -_- . But on a serious note, its very rare to come across somebody who writes this clean code. In case you want to see - [here][9] is his solution. It was really pleasant to read that code, and there are lots of nice tricks which he used. Some of them were damn innovative, hats off to that. [1]: https://www.codechef.com/KGP16MOS/problems/KGP16B [2]: https://www.codechef.com/problems/KGP16B [3]: https://www.codechef.com/users/vijju123 [4]: http://geomalgorithms.com/a03-_inclusion.html [5]: https://www.codechef.com/viewsolution/17245902 [6]:https://www.codechef.com/viewsolution/17235881 [7]: https://www.codechef.com/viewsolution/17245902 [8]: https://www.codechef.com/users/errichto [9]: https://www.codechef.com/viewsolution/17200559