Submission #510722

#	Time	Username	Problem	Language	Result	Execution time	Memory
510722		KoD	Kućice (COCI21_kucice)	C++17	10 / 110	1 ms	376 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) < MOD) 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;
    }
    std::cout << (Fp(N) * Fp(2).pow(N - 1)).x << '\n';
    // 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: 10 / 10
• Subtask 2: 0 / 30
• Subtask 3: 0 / 10
• Subtask 4: 0 / 30
• Subtask 5: 0 / 30