#include "testlib.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

constexpr int kMaxX = 1'000'000'000;

struct TestCase {
    int max_n;
    bool is_convex;
    bool is_random;
    bool is_triangle;
};

vector<TestCase> groups = {
    /* 0: */ TestCase{10000, false, false, false},
    /* 1: */ TestCase{4, false, false, false},
    /* 2: */ TestCase{4, false, false, false},
    /* 3: */ TestCase{10000, false, true, true},
    /* 4: */ TestCase{10000, false, true, true},
    /* 5: */ TestCase{10000, true, false, false},
    /* 6: */ TestCase{100, false, true, false},
    /* 7: */ TestCase{100, false, true, false},
    /* 8: */ TestCase{10000, false, true, false},
    /* 9: */ TestCase{10000, false, true, false},
    /* 10:*/ TestCase{10000, false, false, false},
    /* 11:*/ TestCase{10000, false, false, false},
};

struct vect {
    int x, y;

    vect() = default;

    vect(int x_, int y_) : x(x_), y(y_) {}

    vect operator-(const vect &other) const {
        return vect(x - other.x, y - other.y);
    }

    ll operator^(const vect &other) const {
        return (ll)x * (ll)other.y - (ll)y * (ll)other.x;
    }

    ll operator*(const vect &other) const {
        return (ll)x * (ll)other.x + (ll)y * (ll)other.y;
    }

    bool operator==(const vect &other) const = default;
};

int convex_hull(vector<vect> pt) {
    int idx = 0;
    for (int i = 1; i < (int)pt.size(); i++) {
        if (make_pair(pt[i].y, pt[i].x) < make_pair(pt[idx].y, pt[idx].x)) {
            idx = i;
        }
    }
    swap(pt[0], pt[idx]);
    sort(pt.begin() + 1, pt.end(), [&](const vect &lhs, const vect &rhs) {
        ll cr = (lhs - pt[0]) ^ (rhs - pt[0]);
        if (cr != 0) {
            return cr > 0;
        }
        ll dl = (lhs - pt[0]) * (lhs - pt[0]);
        ll dr = (rhs - pt[0]) * (rhs - pt[0]);
        return dl < dr;
    });
    vector<vect> st;
    for (const auto &p : pt) {
        while (st.size() >= 2 && ((st.back() - st[st.size() - 2]) ^ (p - st[st.size() - 2])) <= 0) {
            st.pop_back();
        }
        st.emplace_back(p);
    }
    return int(st.size());
}

int main(int argc, char **argv) {
    registerValidation(argc, argv);

    string group = validator.group();
    if (group.empty()) {
        group = "0";
    }
    int gid = stoi(group);
    auto tc = groups[gid];

    int n = inf.readInt(4, tc.max_n, "n");
    inf.readSpace();
    inf.readInt(gid, gid, "group");
    inf.readEoln();
    vector<vect> points(n);
    for (int i = 0; i < n; ++i) {
        points[i].x = inf.readInt(-kMaxX, kMaxX, format("x[%d]", i + 1));
        inf.readSpace();
        points[i].y = inf.readInt(-kMaxX, kMaxX, format("y[%d]", i + 1));
        inf.readEoln();
    }

    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            ensuref(points[i].x != points[j].x || points[i].y != points[j].y,
                    "points %d and %d are equal", i + 1, j + 1);
        }
    }

    if (n <= 30) {
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                for (int h = j + 1; h < n; h++) {
                    ensuref(((points[h] - points[i]) ^ (points[j] - points[i])) != 0,
                            "points %d, %d and %d lie on the same line", i + 1, j + 1, h + 1);
                }
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                for (int h = 0; h < n; h++) {
                    for (int p = h + 1; p < n; p++) {
                        if (i == h && j == p) {
                            continue;
                        }
                        ensuref(((points[p] - points[h]) ^ (points[j] - points[i])) != 0,
                                "segment (%d, %d) is parallel to segment (%d, %d)", i + 1, j + 1,
                                h + 1, p + 1);
                    }
                }
            }
        }
    }

    vector<ull> a;
    a.reserve(n * (n - 1) / 2);
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            auto v = points[j] - points[i];
            if (v.y < 0 || (v.y == 0 && v.x < 0)) {
                v.x *= -1;
                v.y *= -1;
            }
            int g = gcd(abs(v.x), abs(v.y));
            v.x /= g;
            v.y /= g;

            ull val = (ull)(v.x + kMaxX) * (ull)(kMaxX + 1) + (ull)(v.y);
            val = val * (ull)(239'239'239) + 123'456'789;
            val ^= val >> 32LL;

            a.emplace_back(val);
        }
    }
    const int n_buckets = 200'000;
    vector<int> cnt(n_buckets + 1);
    for (auto x : a) {
        cnt[(x % n_buckets) + 1]++;
    }
    for (int i = 1; i <= n_buckets; ++i) {
        cnt[i] += cnt[i - 1];
    }
    auto pos = cnt;

    int sz = 0;
    int iters = 8;
    for (int iter = 0; iter < iters; ++iter) {
        int L = (n_buckets * iter) / iters;
        int R = (n_buckets * (iter + 1)) / iters;
        sz = max(sz, pos[R] - pos[L]);
    }
    vector<ull> new_a(sz);
    for (int iter = 0; iter < iters; ++iter) {
        int L = (n_buckets * iter) / iters;
        int R = (n_buckets * (iter + 1)) / iters;
        for (auto x : a) {
            int bucket = (x % n_buckets);
            if (bucket >= L && bucket < R) {
                new_a[(cnt[bucket]++) - pos[L]] = x;
            }
        }

        for (int i = L; i < R; ++i) {
            sort(new_a.begin() + pos[i] - pos[L], new_a.begin() + pos[i + 1] - pos[L]);
            for (int j = pos[i] - pos[L] + 1; j < pos[i + 1] - pos[L]; ++j) {
                ensuref(new_a[j - 1] != new_a[j], "there are two parallel segments between points");
            }
        }
    }

    if (tc.is_convex) {
        ensuref(convex_hull(points) == n, "the points are not on the convex hull");
    }

    if (tc.is_triangle) {
        for (auto p : {vect(kMaxX, -kMaxX), vect(-kMaxX, kMaxX), vect(kMaxX, kMaxX)}) {
            ensuref(find(points.begin(), points.end(), p) != points.end(),
                    "there is no point at (%d, %d)", p.x, p.y);
        }
        for (int i = 0; i < n; i++) {
            ensuref(points[i].x + points[i].y >= 0, "the point %d is not inside the triangle",
                    i + 1);
        }
    }

    inf.readEof();

    return 0;
}
