Submission #510751

#	Time	Username	Problem	Language	Result	Execution time	Memory
510751		KoD	Kućice (COCI21_kucice)	C++17	110 / 110	432 ms	460 KiB

Main

#include <bits/stdc++.h>

using std::vector;
using std::array;
using std::pair;
using std::tuple;

using i64 = std::int64_t;

struct Point {
    int x, y;
    Point() : x(0), y(0) {}
    Point(int x, int y) : x(x), y(y) {}
    friend Point operator-(const Point& p, const Point& q) {
        return Point(p.x - q.x, p.y - q.y);
    }
    friend i64 cross(const Point& p, const Point& q) {
        return (i64)p.x * q.y - (i64)p.y * q.x;
    }
};

constexpr int MOD = 1000000007;

struct Fp {
    int x;
    Fp(int x = 0) : x(x) {}
    Fp& operator+=(const Fp& t) {
        if ((x += t.x) >= MOD) x -= MOD;
        return *this;
    }
    Fp& operator-=(const Fp& t) {
        if ((x -= t.x) < 0) x += MOD;
        return *this;
    }
    Fp& operator*=(const Fp& t) {
        x = (i64)x * t.x % MOD;
        return *this;
    }
    Fp operator+(const Fp& t) const {
        return Fp(*this) += t;
    }
    Fp operator-(const Fp& t) const {
        return Fp(*this) -= t;
    }
    Fp operator*(const Fp& t) const {
        return Fp(*this) *= t;
    }
    Fp pow(int e) const {
        Fp ret(1), mul(*this);
        while (e > 0) {
            if (e & 1) ret *= mul;
            mul *= mul;
            e >>= 1;
        }
        return ret;
    }
    Fp inv() const {
        return pow(MOD - 2);
    }
};

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int N;
    std::cin >> N;
    vector<Point> P(N);
    for (auto& [x, y] : P) {
        std::cin >> x >> y;
    }
    Fp ans = 0;
    for (int pivot = 0; pivot < N; ++pivot) {
        ans += Fp(2).pow(N - 1);
        vector<Point> above, below;
        for (int i = 0; i < N; ++i) {
            if (i != pivot) {
                const Point p = P[i] - P[pivot];
                if (p.y > 0 or (p.x >= 0 and p.y == 0)) {
                    above.push_back(p);
                } else {
                    below.push_back(p);
                }
            }
        }
        std::sort(above.begin(), above.end(), [&](const Point& p, const Point& q) {
            return cross(p, q) > 0;
        });
        std::sort(below.begin(), below.end(), [&](const Point& p, const Point& q) {
            return cross(p, q) > 0;
        });
        const int n = above.size(), m = below.size();
        vector<int> to(n), from(m);
        for (int i = 0, j = 0; i < n; ++i) {
            while (j < m and cross(above[i], below[j]) > 0) {
                j += 1;
            }
            to[i] = j;
        }
        for (int j = 0, i = 0; j < m; ++j) {
            while (i < n and cross(below[j], above[i]) > 0) {
                i += 1;
            }
            from[j] = i;
        }
        // for (int l = 0; l < n; ++l) {
        //     for (int r = to[l]; r < m; ++r) {
        //         const int all = (n - l - 1) + (m - r - 1) + to[l];
        //         const int between = to[l] + (n - from[r]);
        //         ans += Fp(2).pow(all);
        //         ans -= Fp(2).pow(all - between);
        //     }
        // }
        {
            int l = 0;
            Fp coeff = 0;
            for (int r = 0; r < m; ++r) {
                while (l < from[r]) {
                    coeff += Fp(2).pow(l).inv();
                    l += 1;
                }
                ans -= coeff * Fp(2).pow(from[r] - 1 + m - r - 1);
            }
        }
        {
            int r = m;
            Fp coeff = 0;
            for (int l = n - 1; l >= 0; --l) {
                while (to[l] < r) {
                    r -= 1;
                    coeff += Fp(2).pow(r).inv();
                }
                ans += coeff * Fp(2).pow(n - l - 1 + m - 1 + to[l]);
            }
        }
    }
    std::cout << ans.x << '\n';
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 30 / 30
• Subtask 3: 10 / 10
• Subtask 4: 30 / 30
• Subtask 5: 30 / 30