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.