<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

440. Moles and Holes
Time limit per test: 2.25 second(s)
Memory limit: 262144 kilobytes
input: standard
output: standard



N moles live in the cottage of Mr. Tapacob. Every mole lives in its own hole. And Mr. Tapacob is not glad to see them. So he forced them out. But there are three strongest moles, who don't want to leave. They are Shureg, Ruslan and Ruslan. And you should not distinguish Ruslans. Sometimes these three moles poke out of holes to look around. But only one of them, the strangest mole (Shureg), is not blind. And when they peek out from hole, Shureg looks at two other moles. But he is a mole and his vision is strange, therefore he can't see in any angle. The angle between two other moles (let's call it A) must be sharp, and an integer part of value 90 / A (in degrees) must be equal to the third digit after decimal point of decimal representation of .

You are given coordinates of holes. Mr. Tapacob wants to know how many ways are there for moles to peek out from holes such that Shureg can see two other moles. Any mole can get out at any of the holes, but the three holes which they get from must be all different.

Input
First line of input contains integer N (3 ≤ N ≤ 800). Next N lines contain coordinates of holes; each line consists of two integers separated by a space. Coordinates do not exceed 1000 by absolute value. No two holes coincide.

Output
Output one integer — the number of ways.

Example(s)
sample input
sample output
10
628 1
17 207
176 1
16 -5
161 0
-1 56
17 83
1 5
15 1
18 101
15

<|response|>
## 1) Abridged problem statement (concise)

You are given **N (3 ≤ N ≤ 800)** distinct points (holes) on the plane.

Choose **three distinct holes** and assign:
- Shureg (the only seeing mole) to hole **P**,
- the two other moles (indistinguishable) to holes **Q** and **R**.

Let **A = ∠QPR** be the angle at **P** between rays **PQ** and **PR** (in degrees).  
This choice is valid if:

1) **A is acute**: \(0 < A < 90^\circ\)  
2) \(\left\lfloor \frac{90}{A} \right\rfloor\) equals the **3rd digit after the decimal point** of \(\cos(A)\), i.e.
\[
\left\lfloor \frac{90}{A} \right\rfloor \;=\; \Big(\lfloor 1000\cos(A)\rfloor \bmod 10\Big)
\]

Count the number of valid **ordered** triples \((P,Q,R)\) with all points distinct (Q and R are “the two Ruslans” but holes are still chosen, so \((P,Q,R)\) and \((P,R,Q)\) both count if valid).

---

## 2) Key observations

### Geometry reformulation
For a fixed pivot \(P\), define vectors:
- \(\vec u = Q - P\)
- \(\vec v = R - P\)

Then:
- Acute angle ⇔ \(\vec u \cdot \vec v > 0\)
- \(\cos(A) = \dfrac{\vec u \cdot \vec v}{\|\vec u\|\|\vec v\|}\)

So the condition depends only on the angle between two rays from the same pivot.

### The “weird condition” only allows few angle intervals
Let:
\[
k = \left\lfloor \frac{90}{A} \right\rfloor
\]
For acute \(A\in(0,90)\), relevant values for the equality with a decimal digit end up being only **k = 1..9** (because the right side is a digit 0..9, and k can’t be 0 for acute angles).

For each fixed \(k\), the angle must lie in the slice:
\[
A \in \left(\frac{90}{k+1}, \frac{90}{k}\right]
\]
Inside this slice, \(\cos(A)\) is monotone, and the constraint
\[
\lfloor 1000\cos(A)\rfloor \bmod 10 = k
\]
means
\[
1000\cos(A)\in [10m+k,\;10m+k+1)
\]
for some integer \(m\). Intersecting these with the cosine range of the slice yields **a small set of disjoint angle sub-intervals**. Total count across all \(k\) is small (≈ up to a few hundred).

### Counting can be reduced to “angles in intervals”
Fix pivot \(P\). Sort all other points by polar angle \(\theta\) around \(P\).  
Then for a fixed ray to \(Q\) (angle \(\theta_Q\)), the ray to \(R\) is valid iff:
\[
\theta_R \in \theta_Q + [a_{lo}, a_{hi})
\]
for one of the precomputed allowed intervals.

This becomes a classic **two-pointers / sweeping** problem on a circularly sorted angle array (handled by duplicating with +\(2\pi\)).

### Need exact verification (floating-point pitfalls)
We use floating angles only to locate candidates; final acceptance must be **exact**:
- Check acute with integer dot product.
- Compute \(F=\lfloor 1000\cos(A)\rfloor\) robustly using integer inequalities:
  \[
  \left(\lfloor 1000\cos(A)\rfloor\right)^2 \cdot \|u\|^2\|v\|^2 \le (1000(u\cdot v))^2
  \]
  and correct a double-based guess by ±1 steps.
- Compute \(k=\lfloor 90/A\rfloor\) without computing \(A\) directly: compare \(\cos^2(A)\) with precomputed thresholds \(\cos^2(90/k)\).

---

## 3) Full solution approach

### Step A — Precompute allowed angle intervals
For each \(k=1..9\):
1) Angle slice where \(k=\lfloor 90/A\rfloor\):
   \[
   A \in \left(\frac{90}{k+1},\frac{90}{k}\right]
   \]
2) Corresponding cosine range:
   \[
   \cos(A)\in [\cos(90/k),\; \cos(90/(k+1))]
   \]
3) For integers \(m\), enforce digit condition:
   \[
   1000\cos(A)\in [10m+k,\; 10m+k+1)
   \]
   i.e.
   \[
   \cos(A)\in \left[\frac{10m+k}{1000},\;\frac{10m+k+1}{1000}\right)
   \]
4) Intersect this cosine interval with the slice cosine range, convert back to angles using acos (note acos is decreasing), and store resulting angle intervals in radians.
5) Slightly **relax** interval endpoints by a tiny epsilon (e.g. 1e-9) so we don’t miss borderline candidates during sweeps.

### Step B — For each pivot P, count pairs (Q,R)
For each pivot point \(P\):
1) Build vectors to all other points, store their polar angles \(\theta\in[-\pi,\pi)\).
2) Sort by \(\theta\). Duplicate list with \(\theta+2\pi\) to handle wrap-around.
3) For each base index \(j\) in the first \(m=N-1\) rays (i.e., \(Q\)):
   - For each allowed interval \([lo,hi)\):
     - Maintain two pointers `L` and `R` that locate the range of rays whose angles lie in \(\theta_Q+[lo,hi)\).
     - Add \((R-L)\) to answer, but first **trim** false positives near boundaries by exact checking:
       - while leftmost candidate fails `check`, increment L
       - while rightmost candidate fails `check`, decrement R  
       After trimming, count remaining.
4) Sum across pivots.

Complexity:
- Sorting per pivot: \(O(N\log N)\)
- Sweeping per pivot: \(O(N \cdot K)\) where \(K\) = number of precomputed intervals (small)
- Total: \(O(N^2\log N + N^2 K)\), feasible for \(N=800\).

---

## 4) C++ implementation (detailed comments)

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

// ------------------------------------------------------------
// Point / vector (we store coordinates as doubles, but note that
// all input coordinates are integers. Differences are integers.)
// ------------------------------------------------------------
struct Point {
    double x, y;
    Point(double x=0, double y=0) : x(x), y(y) {}
    Point operator-(const Point& other) const { return Point(x - other.x, y - other.y); }
    double angle() const { return atan2(y, x); } // polar angle in radians
};

struct Interval { double lo, hi; }; // radians, [lo, hi)
static vector<Interval> allowed;

// ------------------------------------------------------------
// Precompute all angle sub-intervals where the condition could hold.
// We consider k = floor(90/A) in [1..9], because rhs is a digit.
// For each k, restrict A into (90/(k+1), 90/k] and enforce
// floor(1000*cos(A)) % 10 == k via cosine bands.
// ------------------------------------------------------------
static void precompute_intervals() {
    const double PI = acos(-1.0);
    const double DEG = PI / 180.0;

    for (int k = 1; k <= 9; k++) {
        double a_lo_deg = 90.0 / (k + 1);
        double a_hi_deg = 90.0 / k;

        // On this slice, cos decreases as A increases.
        // Max cosine at smaller angle:
        double cos_hi = cos(a_lo_deg * DEG);
        // Min cosine at larger angle:
        double cos_lo = cos(a_hi_deg * DEG);

        // We need 1000*cos(A) in [10m+k, 10m+k+1).
        // Find m range that could intersect [1000*cos_lo, 1000*cos_hi].
        int m_min = (int)floor((cos_lo * 1000.0 - k) / 10.0) - 1;
        int m_max = (int)ceil ((cos_hi * 1000.0 - k) / 10.0) + 1;

        for (int m = m_min; m <= m_max; m++) {
            // Candidate cosine band from digit constraint:
            double band_lo = (10 * m + k)     / 1000.0;
            double band_hi = (10 * m + k + 1) / 1000.0; // open on the right conceptually

            // Intersect with slice cosine range:
            double c_lo = max(band_lo, cos_lo);
            double c_hi = min(band_hi, cos_hi);
            if (c_lo >= c_hi) continue; // empty

            // Convert cosine interval back to angle interval.
            // Since acos is decreasing:
            // cos in [c_lo, c_hi] corresponds to A in [acos(c_hi), acos(c_lo)].
            double a_int_lo = acos(min(c_hi, 1.0));
            double a_int_hi = acos(max(c_lo, 0.0));

            // Clip back to the original slice (in radians):
            a_int_lo = max(a_int_lo, a_lo_deg * DEG);
            a_int_hi = min(a_int_hi, a_hi_deg * DEG);
            if (a_int_lo >= a_int_hi) continue;

            // Relax a bit to avoid missing candidates due to floating errors in sweeps.
            allowed.push_back({a_int_lo - 1e-9, a_int_hi + 1e-9});
        }
    }
}

// ------------------------------------------------------------
// Exact checker for a pair of vectors u, v from the same pivot.
// Input vectors are stored as doubles, but represent integer dx,dy.
// We use int64 for dot and squared lengths (safe for coordinate bounds).
//
// Conditions:
// 1) acute: dot > 0
// 2) lhs = floor(90/A) equals rhs = floor(1000*cos(A)) % 10
//
// rhs is computed robustly by correcting a float guess using integer inequality:
//   F <= 1000*cos(A)  <=>  F^2 * |u|^2|v|^2 <= (1000*dot)^2
//
// lhs is derived by comparing cos^2(A) to precomputed boundaries of cos^2(90/k).
// ------------------------------------------------------------
static bool check_pair(const Point& u, long long L1,
                       const Point& v, long long L2,
                       const double cos2_bound[11]) {
    long long dot = (long long)(u.x * v.x + u.y * v.y);
    if (dot <= 0) return false; // not acute

    using i128 = __int128_t;

    // D = 1000*dot, compare against F*sqrt(L1*L2)
    i128 D  = (i128)1000 * dot;
    i128 D2 = D * D;
    i128 L1L2 = (i128)L1 * L2;

    // Float approximation:
    int F = (int)floor(1000.0 * (double)dot / sqrt((double)L1 * (double)L2));

    // Correct downward if too big:
    while (F > 0 && (i128)F * F * L1L2 > D2) F--;
    // Correct upward if too small:
    while ((i128)(F + 1) * (F + 1) * L1L2 <= D2) F++;

    if (F >= 1000) return false; // would imply cos(A) >= 1, impossible for distinct points
    int rhs = F % 10;

    // Determine lhs = floor(90/A) without computing A:
    // A in (90/(k+1), 90/k]  <=> cos(A) in [cos(90/k), cos(90/(k+1)))
    // For acute angles cos(A)>0, so squaring preserves ordering.
    double cos2_a = (double)dot * (double)dot / ((double)L1 * (double)L2);

    int lhs = 0;
    for (int k = 9; k >= 1; k--) {
        if (cos2_a >= cos2_bound[k] - 1e-12) {
            if (cos2_a < cos2_bound[k + 1] + 1e-12) lhs = k;
            break;
        }
    }

    return lhs > 0 && lhs == rhs;
}

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

    precompute_intervals();

    int N;
    cin >> N;
    vector<Point> pts(N);
    for (int i = 0; i < N; i++) cin >> pts[i].x >> pts[i].y;

    const double PI = acos(-1.0);
    const double TWO_PI = 2.0 * PI;
    const double DEG = PI / 180.0;

    // Precompute cos^2(90/k) for k=1..10 (10 is needed for upper boundary checks)
    double cos2_bound[11] = {};
    for (int k = 1; k <= 10; k++) {
        double c = cos((90.0 / k) * DEG);
        cos2_bound[k] = c * c;
    }

    long long ans = 0;
    const int K = (int)allowed.size();

    // Pivot P = pts[i]
    for (int i = 0; i < N; i++) {
        int M = N - 1;

        // Collect all rays from pivot to other points
        vector<double> ang(M);
        vector<Point>  vec(M);
        vector<long long> len2(M);

        int idx = 0;
        for (int j = 0; j < N; j++) if (j != i) {
            Point d = pts[j] - pts[i]; // integer dx,dy in double container
            vec[idx] = d;
            ang[idx] = d.angle();
            len2[idx] = (long long)(d.x * d.x + d.y * d.y);
            idx++;
        }

        // Sort indices by angle
        vector<int> order(M);
        iota(order.begin(), order.end(), 0);
        sort(order.begin(), order.end(), [&](int a, int b){ return ang[a] < ang[b]; });

        // Build doubled arrays to avoid wrap-around
        vector<double> ext_ang(2 * M);
        vector<int>    ext_id (2 * M); // index into vec/len2
        for (int t = 0; t < M; t++) {
            ext_ang[t]     = ang[order[t]];
            ext_ang[t + M] = ang[order[t]] + TWO_PI;
            ext_id[t]      = order[t];
            ext_id[t + M]  = order[t];
        }

        // Two pointers per allowed interval (monotone as base angle increases)
        vector<int> ptrL(K, 0), ptrR(K, 0);

        // For each base ray Q in the first M positions:
        for (int j = 0; j < M; j++) {
            double base = ext_ang[j];
            int qid = ext_id[j];

            for (int t = 0; t < K; t++) {
                double lo = base + allowed[t].lo;
                double hi = base + allowed[t].hi;

                while (ptrL[t] < 2 * M && ext_ang[ptrL[t]] < lo) ptrL[t]++;
                while (ptrR[t] < 2 * M && ext_ang[ptrR[t]] < hi) ptrR[t]++;

                int L = ptrL[t];
                int R = ptrR[t];

                // Trim left boundary (because intervals were relaxed)
                while (L < R) {
                    int rid = ext_id[L];
                    if (check_pair(vec[qid], len2[qid], vec[rid], len2[rid], cos2_bound)) break;
                    L++;
                }
                // Trim right boundary
                while (L < R) {
                    int rid = ext_id[R - 1];
                    if (check_pair(vec[qid], len2[qid], vec[rid], len2[rid], cos2_bound)) break;
                    R--;
                }

                if (L < R) ans += (R - L);
            }
        }
    }

    cout << ans << "\n";
    return 0;
}
```

---

## 5) Python implementation (detailed comments)

```python
import math

# ------------------------------------------------------------
# Precompute allowed angle intervals (radians) where condition can hold.
# Same logic as C++.
# ------------------------------------------------------------
def precompute_intervals():
    PI = math.acos(-1.0)
    DEG = PI / 180.0
    allowed = []

    for k in range(1, 10):
        a_lo_deg = 90.0 / (k + 1)
        a_hi_deg = 90.0 / k

        cos_hi = math.cos(a_lo_deg * DEG)  # max cos in slice
        cos_lo = math.cos(a_hi_deg * DEG)  # min cos in slice

        m_min = int(math.floor((cos_lo * 1000.0 - k) / 10.0)) - 1
        m_max = int(math.ceil ((cos_hi * 1000.0 - k) / 10.0)) + 1

        for m in range(m_min, m_max + 1):
            band_lo = (10 * m + k) / 1000.0
            band_hi = (10 * m + k + 1) / 1000.0

            c_lo = max(band_lo, cos_lo)
            c_hi = min(band_hi, cos_hi)
            if c_lo >= c_hi:
                continue

            # acos is decreasing
            a_int_lo = math.acos(min(c_hi, 1.0))
            a_int_hi = math.acos(max(c_lo, 0.0))

            a_int_lo = max(a_int_lo, a_lo_deg * DEG)
            a_int_hi = min(a_int_hi, a_hi_deg * DEG)
            if a_int_lo >= a_int_hi:
                continue

            allowed.append((a_int_lo - 1e-9, a_int_hi + 1e-9))

    return allowed


ALLOWED = precompute_intervals()


# ------------------------------------------------------------
# Precompute cos^2(90/k degrees) for k=1..10.
# Used to determine lhs = floor(90/A) from cos^2(A).
# ------------------------------------------------------------
def cos2_bounds():
    PI = math.acos(-1.0)
    DEG = PI / 180.0
    b = [0.0] * 11
    for k in range(1, 11):
        c = math.cos((90.0 / k) * DEG)
        b[k] = c * c
    return b


COS2_BOUND = cos2_bounds()


# ------------------------------------------------------------
# Exact check of a pair of vectors u=(dx1,dy1), v=(dx2,dy2).
# dx,dy and squared lengths are integers (in Python int).
#
# Robustly compute F = floor(1000*cos(A)) by correcting a float guess using:
#   F^2 * (L1*L2) <= (1000*dot)^2
# ------------------------------------------------------------
def check(dx1, dy1, L1, dx2, dy2, L2):
    dot = dx1 * dx2 + dy1 * dy2
    if dot <= 0:
        return False  # not acute

    D = 1000 * dot
    D2 = D * D
    L1L2 = L1 * L2

    # float guess
    F = int(math.floor(1000.0 * dot / math.sqrt(float(L1L2))))

    # correct
    while F > 0 and (F * F) * L1L2 > D2:
        F -= 1
    while ((F + 1) * (F + 1)) * L1L2 <= D2:
        F += 1

    if F >= 1000:
        return False
    rhs = F % 10

    cos2_a = (dot * dot) / float(L1L2)

    lhs = 0
    for k in range(9, 0, -1):
        if cos2_a >= COS2_BOUND[k] - 1e-12:
            if cos2_a < COS2_BOUND[k + 1] + 1e-12:
                lhs = k
            break

    return lhs > 0 and lhs == rhs


# ------------------------------------------------------------
# Main solver: for each pivot P, sort rays by angle and sweep allowed intervals.
# Complexity ~ O(N^2 log N + N^2*K) with small K.
# ------------------------------------------------------------
def solve(points):
    n = len(points)
    PI = math.acos(-1.0)
    TWO_PI = 2.0 * PI
    K = len(ALLOWED)
    ans = 0

    for i in range(n):
        px, py = points[i]

        rays = []  # (angle, dx, dy, L)
        for j in range(n):
            if j == i:
                continue
            x, y = points[j]
            dx = x - px
            dy = y - py
            ang = math.atan2(dy, dx)
            L = dx * dx + dy * dy
            rays.append((ang, dx, dy, L))

        rays.sort(key=lambda t: t[0])
        m = n - 1

        # Duplicate angles with +2pi
        ext_ang = [0.0] * (2 * m)
        ext_dx  = [0]   * (2 * m)
        ext_dy  = [0]   * (2 * m)
        ext_L   = [0]   * (2 * m)

        for t in range(m):
            ang, dx, dy, L = rays[t]
            ext_ang[t] = ang
            ext_dx[t] = dx
            ext_dy[t] = dy
            ext_L[t] = L

            ext_ang[t + m] = ang + TWO_PI
            ext_dx[t + m] = dx
            ext_dy[t + m] = dy
            ext_L[t + m] = L

        # Two pointers per interval
        ptrL = [0] * K
        ptrR = [0] * K

        for j in range(m):
            base = ext_ang[j]
            qdx, qdy, qL = ext_dx[j], ext_dy[j], ext_L[j]

            for t in range(K):
                lo = base + ALLOWED[t][0]
                hi = base + ALLOWED[t][1]

                p = ptrL[t]
                while p < 2 * m and ext_ang[p] < lo:
                    p += 1
                ptrL[t] = p

                p = ptrR[t]
                while p < 2 * m and ext_ang[p] < hi:
                    p += 1
                ptrR[t] = p

                L = ptrL[t]
                R = ptrR[t]

                # Trim boundaries using exact check (interval endpoints are relaxed)
                while L < R:
                    if check(qdx, qdy, qL, ext_dx[L], ext_dy[L], ext_L[L]):
                        break
                    L += 1
                while L < R:
                    if check(qdx, qdy, qL, ext_dx[R - 1], ext_dy[R - 1], ext_L[R - 1]):
                        break
                    R -= 1

                if L < R:
                    ans += (R - L)

    return ans


# ------------------------------------------------------------
# I/O
# ------------------------------------------------------------
if __name__ == "__main__":
    import sys
    data = sys.stdin.read().strip().split()
    n = int(data[0])
    pts = []
    it = iter(data[1:])
    for x, y in zip(it, it):
        pts.append((int(x), int(y)))
    print(solve(pts))
```

---

If you want, I can also provide a short “sanity-check” section (why k only needs 1..9, why trimming endpoints is safe in practice, and typical size of `allowed`).