QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#836442#9924. Reconstructionucup-team6275#WA 0ms3804kbC++173.9kb2024-12-28 20:46:592024-12-28 20:47:00

Judging History

你现在查看的是最新测评结果

  • [2024-12-31 17:12:54]
  • hack成功,自动添加数据
  • (/hack/1320)
  • [2024-12-28 20:47:00]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3804kb
  • [2024-12-28 20:46:59]
  • 提交

answer

#include <iostream>
#include <vector>
#include <array>
#include <string>
#include <algorithm>
#include <iomanip>
#include <map>

using namespace std;
#define ll long long

struct point {
    ll x, y;

    ll len2() {
        return x * x + y * y;
    }
};

bool operator<(point a, point b) {
    return make_pair(a.x, a.y) < make_pair(b.x, b.y);
}

point operator-(point a, point b) {
    return {a.x - b.x, a.y - b.y};
}

point operator+(point a, point b) {
    return {a.x - b.x, a.y - b.y};
}

ll operator%(point a, point b) {
    return a.x * b.y - a.y * b.x;
}

int sign(ll x) {
    if (x > 0) return 1;
    if (x == 0) return 0;
    return -1;
}

vector<point> convexHull(vector<point> p) {
    if (p.empty()) {
        return {};
    }
    int n = p.size();
    int pos = min_element(p.begin(), p.end()) - p.begin();
    swap(p[0], p[pos]);
    for (int i = 1; i < n; ++i)
        p[i] = p[i] - p[0];
    sort(p.begin() + 1, p.end(), [&](point &lhs, point &rhs) -> bool {
        int sgn = sign(lhs % rhs);
        if (!sgn) {
            return lhs.len2() < rhs.len2();
        }
        return sgn == 1;
    });
    for (int i = 1; i < n; ++i)
        p[i] = p[i] + p[0];
    int top = 0;
    for (int i = 0; i < n; ++i) {
        while (top >= 2) {
            point v1 = p[top - 1] - p[top - 2];
            point v2 = p[i] - p[top - 1];
            if (v1 % v2 > 0)
                break;
            --top;
        }
        p[top++] = p[i];
    }
    p.resize(top);
    return p;
}

ll calc_sq(vector <point>& a) {
    ll ans = 0;
    int n = a.size();
    for (int i = 1; i < n - 1; ++i) {
        ans += (a[i] - a[0]) % (a[i + 1] - a[0]);
    }
    return abs(ans);
}

int half(point a) {
    if (a.y > 0 || (a.y == 0 && a.x > 0)) return 0;
    return 1;
}

bool cmp(point a, point b) {
    int h1 = half(a);
    int h2 = half(b);
    if (h1 != h2) return h1 < h2;
    return a % b > 0;
}

const ll mod = 1e9 + 7;

inline int mul(int a, int b) {
    return 1ll * a * b % mod;
}

inline int power(int a, int pw) {
    int ans = 1;
    while (pw) {
        if (pw & 1) {
            ans = mul(ans, a);
        }
        a = mul(a, a);
        pw >>= 1;
    }
    return ans;
}

inline int inv(int x) {
    return power(x, mod - 2);
}

inline int add(int a, int b) {
    a += b;
    if (a >= mod) a -= mod;
    return a;
}

inline int sub(int a, int b) {
    a -= b;
    if (a < 0) a += mod;
    return a;
}

void solve() {
    int n;
    cin >> n;
    vector <point> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i].x >> a[i].y;

    auto ch = convexHull(a);
    map <pair <ll, ll>, int> isc;

    for (auto i : ch) {
        isc[make_pair(i.x, i.y)] = 1;
    }

    ll S = calc_sq(ch);
//    int inv2 = inv(2);
    int ln = ch.size();
    vector <point> vecs;
    int answer = 0;

    for (auto i : a) {
        if (isc.count(make_pair(i.x, i.y))) continue;

        vector <int> banned(ln);
        for (int j = 0; j < ch.size(); ++j) {
            vecs.push_back(ch[j] - i);
        }

        sort(vecs.begin(), vecs.end(), cmp);

        for (auto j : a) {
            if (isc.count(make_pair(j.x, j.y)) || (i.x == j.x && i.y == j.y)) continue;

            auto it = lower_bound(vecs.begin(), vecs.end(), j, cmp);
            int kek = (it - vecs.begin()) % ln;
            banned[kek] = 1;
        }

        for (int j = 0; j < ln; ++j) {
            if (banned[j]) continue;
            answer = add(answer, S);
            int prv = (j - 1 + ln) % ln;
            ll S2 = abs(vecs[prv] % vecs[j]);
            S2 %= mod;
            answer = sub(answer, S2);
        }
    }

    cout << answer;
}

signed main() {
    if (1) {
        ios_base::sync_with_stdio(false);
        cin.tie(nullptr);
    }
    int t = 1;
//    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

/*
4
0 0
2 0
1 2
1 1
 */

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 3804kb

input:

3
1 2
2 3
2 1
1 3

output:

1000000003

result:

wrong answer 1st lines differ - expected: '001', found: '1000000003'