### PROBLEM LINK:

**Authors:** Praveen Dhinwa

**Testers:** Jingbo Shang, Istvan Nagy

**Editorialist:** Vaibhav Tulsyan

### PROBLEM

Given N points (x_i, y_i) in the 2D-plane, check if any 3 consecutive points A(x_{i - 1}, y_{i - 1}), B(x_i, y_i), C(x_{i + 1}, y_{i + 1}) have \angle ABC \le 135^{\circ}.

#### Constraints:

1 \le T \le 50

3 \le N \le 50

0 \le x_i, y_i \le 50

All (x_i, y_i) pairs are distinct.

### EXPLANATION

Though the problem idea was not that difficult, many people got scared by geometry may be and didn’t solve it much during the contest.

The idea was very simple. First, we find whether the taxi made a sharp turn or not. If it makes a sharp turn at i^{th} step, then we can try 4 indices j (2 before and 2 after i) and try assigning them coordinates (x, y) in the range [0, 50] by pure bruteforce. This way, total time complexity will be \mathcal{O}(5 * 50^2 * 50) per test case.

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

Author’s solution can be found here.

Tester 1’s solution can be found here.

Tester 2’s solution can be found here.