Submission #510730

#	Time	Username	Problem	Language	Result	Execution time	Memory
510730		KoD	Kućice (COCI21_kucice)	C++17	40 / 110	1087 ms	360 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;
    }
};

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);
            }
        }
    }
    std::cout << ans.x << '\n';
    return 0;
}

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