HackerRank Geometry – The Letter N

Challenge: The Letter N

Scor cont: 80.0 / 80

Submission status: Accepted

Submission score: 1.0

Submission ID: 464802053

Limbaj: cpp14

Link challenge: https://www.hackerrank.com/challenges/n-letter/problem

Cerinta

Little Nina is learning to read. Her favorite letter is `N`, and she looks for it everywhere.

There is a set of $N$ points on the plane. Let's consider four different points from the set and name them $A$, $B$, $C$, and $D$ (in that order). Nina says that these four points form the letter `N` if all the following conditions are met:

1. $A$ is located strictly to the right of ray $\overrightarrow{BC}$ (in this order).
2. $D$ is located strictly to the left of ray $\overrightarrow{BC}$ (in this order).
3. Angle $\angle ABC \le 90°$ 
4. Angle $\angle BCD \le 90°$

How many `N`s can she find? We consider letters to be sets of four points, and two letters differ if the value of one or more of the points (i.e., $A, B, C$, or $D$) differs between the two corresponding sets of points. For example, if two sets of points have differing $A$ values, then they are different letters. In addition, letters that can be transformed into each other only by reversing point order are considered to be the same letter.

Input Format

The first line contains a single integer, $N$, denoting the number of points.		
Each line $i$ of the $N$ subsequent lines contain two space-separated integers, $x_i$ and $y_i$, describing the respective coordinates of point $(x_i, y_i)$. *No two points coincide.*

Output Format

Print a single integer denoting the number of different `N`s.

Constraints

- $4 \le N \le 2318$
- $-10^4 \le x_i, y_i \le 10^4$

Cod sursa

#include <bits/stdc++.h>
using namespace std;

struct Dir {
    long double ang;
    int id;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;
    vector<long long> X(n), Y(n);
    for (int i = 0; i < n; ++i) cin >> X[i] >> Y[i];

    const long double PI = acosl(-1.0L);
    const long double TWO_PI = 2.0L * PI;
    const long double HALF_PI = PI / 2.0L;
    const long double EPS = 1e-18L;

    vector<vector<int>> cnt(n, vector<int>(n, 0));

    vector<Dir> a;
    a.reserve(n - 1);

    for (int b = 0; b < n; ++b) {
        a.clear();
        for (int j = 0; j < n; ++j) if (j != b) {
            long double dx = (long double)X[j] - X[b];
            long double dy = (long double)Y[j] - Y[b];
            long double ang = atan2l(dy, dx);
            if (ang < 0) ang += TWO_PI;
            a.push_back({ang, j});
        }

        sort(a.begin(), a.end(), [](const Dir& u, const Dir& v) {
            if (u.ang != v.ang) return u.ang < v.ang;
            return u.id < v.id;
        });

        int m = (int)a.size();
        vector<Dir> w(2 * m);
        for (int i = 0; i < m; ++i) {
            w[i] = a[i];
            w[i + m] = {a[i].ang + TWO_PI, a[i].id};
        }

        int l = 0;
        for (int g = m; g < 2 * m; ) {
            int h = g + 1;
            while (h < 2 * m && fabsl(w[h].ang - w[g].ang) <= EPS) ++h;

            long double low = w[g].ang - HALF_PI;
            while (l < g && w[l].ang + EPS < low) ++l;

            int val = g - l;
            for (int i = g; i < h; ++i) {
                cnt[b][w[i].id] = val;
            }
            g = h;
        }
    }

    long long ans = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            ans += 1LL * cnt[i][j] * cnt[j][i];
        }
    }

    cout << ans << '\n';
    return 0;
}