### PROBLEM LINK:

**Setter:** Hasan Jaddouh

**Tester:** Misha Chorniy

**Editorialist:** Taranpreet Singh

### DIFFICULTY:

Easy-Medium

### PREREQUISITES:

Trigonometry and Basic Data Structures.

### PROBLEM:

Given a sequence A of length N, choose any three distinct elements A_x, A_y and A_z such that

- |XY| = A_z, |XZ| = A_y, |YZ| = A_x
- The angle ∠YXZ = θ satisfies \cos θ \geq P/Q

If there are multiple triangles satisfying above, choose the one which results in maximum angle θ. Find such a triangle or determine that it does not exist.

### SUPER QUICK EXPLANATION

- Law of cosines state that if |XY| = z, |XZ| = y, |YZ| = x, then z^2 = x^2 + y^2 - 2*x*y*\cos θ.
- Since we need \cos θ \geq P/Q, we rearrange law of cosines to get z^2*Q \leq (x^2+y^2)*Q - 2*x*y*P. We also need to check if the sum of two sides is greater than the third side.
- We fix two elements x and y and try to find z using binary search (preferred) or lower bound on sets. If multiple triangles we find, we take the one with the minimum value of \cos θ as \cos θ and θ are inversely related.

### EXPLANATION

First of all, I am explaining the Law of cosines, which states that

If |XY| = z, |XZ| = y, |YZ| = x, then z^2 = x^2 + y^2 - 2*x*y*\cos θ.

Since we have N \leq 1000, we can fix two sides of triangle XYZ, say XY and XZ, and try to find a side for which \cos θ \geq P/Q.

Let us write the inequality in terms of \cos θ.

\cos θ = \frac {x^2+y^2-z^2}{2*x*y} \geq \frac{P}{Q}

After reaarranging the terms of inequality, we get

z^2*Q \leq (x^2+y^2)*Q-2*x*y*P

We have all terms except z in above inequality. Also, notice, that since Q \geq 1 and z \geq 1, Q*z^2 is an increasing function of z and thus, if we sort the sides by non-decreasing order of length, only segments from the start upto a particular segment will satisfy above inequality, depending upon values of x, y, P and Q.

This gives way to Binary Search if we sort the given sides, we can use binary search to find the side. Additional check is required to make sure that we do not select the same side twice (in case we had chosen the side we found already as x or y.) or checking if this combination of sides (x, y, z) satisfies **Triangle Inequality Theorem** which states that sum of any two sides should be greater than third side. You may read about triangle inequality here if you want to.

Now, suppose we have multiple answer, so, how to find which triangle results in larger value of θ. For this, we need to understand the behaviour of \cos θ as θ increases, in range [0, 180). We can find, that the cos function is strictly decreasing function in this range, hence, we can just see, that **to maximize θ, we need to minimize \cos θ.**

Every time we hit a valid triangle, we can just apply **Law of Cosine** again to find the value of \cos θ, and choose the one with minimum value of θ.

In case we do not find a valid triangle, we simply print -1.

To print indices, we can make values as (value, index) pairs sorted by value so that we can find index of values easily.

**Alternative Implementation**

We can just use multiset, iterate over every pair (x,y), remove both from set and make lower_bound query to find the third side. After query, we add the removed elements back and continue.

Note that the insert and delete operations increase the constant factor a lot, and thus, may work slower than binary search. Just mentioned this, as a side thought.

**Another Rant from Editorialist**

Though it is rare to see such type of problems, it never hurts to know basics of trigonometry, about increasing and decreasing functions, concept of local maxima and local minima and so on. These are usually worth a read.

### Time Complexity

Time complexity is O(N^2*logN) per test case. Log factors due to multiset operations.

### AUTHOR’S AND TESTER’S SOLUTIONS:

Setter’s solution

Tester’s solution

Editorialist’s solution

Feel free to Share your approach, If it differs. Suggestions are always welcomed.