# TAXITURN - Editorial

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.

The solutions provided here directs to some other solution. Not this TAXITURN.cpp. please correct it.

any explaination for the 4 values of j? please.