YS - Sort Points by Argument

Solution

The idea for this problem is fairly straightforward. Let us define the "argument" of a point as the angle it forms with the origin. Given $n$ points $\{P_1,...,P_n\}$, we can find the argument of the point $P_i = (x_i,y_i)$ by calling $\tan^{-1}{\frac{y_i}{x_i}}$. To sort the points in the counterclockwise order, we just sort the points based on their argument from smallest to largest.

The problem conviently required us to have the sorted points start from the 3rd quadrant and end at the 2nd quadrant, which matches with the characteristics of the builtin $\tan^{-1}$ function, where the 3rd and 4th quadrant points have negative angle values and 1st and 2nd quadrant points have positive angle values.

Implementation

Time Complexity: $\mathcal{O}(N \log N \cdot M(N))$, where $M(N)$ is the computation complexity for $\tan^{-1}{N}$

Copy
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

struct Point {
	ll x;
	ll y;
};

int main() {