### 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.

**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 . 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-

- When Jared can go straight to Payton
- When Jared has to move across 1 vertex to go to payton. (Goto Vertex A and from there to Payton)
- 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).
- 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

[

]

6

p

i

[

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

i

[

%4