QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#456389#7131. Random pointspropaneWA 1ms3724kbC++203.0kb2024-06-27 20:40:422024-06-27 20:40:42

Judging History

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

  • [2024-06-27 20:40:42]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3724kb
  • [2024-06-27 20:40:42]
  • 提交

answer

#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
using LL = long long;

const int maxn = 2005, mod = 1e9 + 7;

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

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

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

int pow2[maxn];

struct Point{
    LL x, y;

    bool operator==(const Point &t) const {
        return x == t.x and y == t.y;
    }

    Point operator-(const Point &t) const {
        return {x - t.x, y - t.y};
    }

    LL operator*(const Point &t) const {
        return x * t.x + y * t.y;
    }

    LL operator^(const Point &t) const {
        return x * t.y - y * t.x;
    }

    int quad() const {
        if (y < 0) return 1;
        if (y > 0) return 4;
        if (x > 0) return 2;
        if (x < 0) return 5;
        return 3;
    }

    bool operator<(const Point &t) const {
        int q1 = quad(), q2 = t.quad();
        if (q1 != q2) return q1 < q2;
        return (*this ^ t) > 0;
    }

};

int main(){

#ifdef LOCAL
    freopen("data.in", "r", stdin);
    freopen("data.out", "w", stdout);
#endif

    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);

    pow2[0] = 1;
    for(int i = 1; i < maxn; i++){
        pow2[i] = mul(pow2[i - 1], 2);
    }

    int n;
    cin >> n;
    vector<Point> p(n);
    for(int i = 0; i < n; i++){
        cin >> p[i].x >> p[i].y;
    }
    sort(p.begin(), p.end());
    p.erase(unique(p.begin(), p.end()), p.end());
    int ans = 0;

    // 枚举每个点,计算其出现但是不在凸包上的方案数
    for(int i = 0; i < p.size(); i++){
        vector<Point> q;
        q.reserve(p.size());
        for(auto pt : p){
            if (pt != p[i]){
                q.push_back(pt - p[i]);
            }
        }
        sort(q.begin(), q.end());

        auto check1 = [&](int x, int y){
            LL t = q[x] ^ q[y];
            if (t > 0) return true;
            if (t < 0) return false;
            return (q[x] * q[y]) > 0;
        };

        auto check2 = [&](int x, int y){
            LL t = p[x] ^ p[y];
            return t >= 0;
        };

        int sum = 0;
        for(int i = 0, j = 0, k = 0; i < q.size(); i++){
            j = max(j, i);
            k = max(k, i);
            while(j < q.size() and check1(i, j)) j++;
            while(k < q.size() and check2(i, k)) k++;
            int c1 = j - i - 1;
            int c2 = k - j;
            int c3 = int(q.size()) - k;
            // 取正好形成平角的点,剩下的任取
            add(sum, mul(sub(pow2[c2], 1), pow2[c1 + c3]));
            // 不取形成平角的点,剩下的两种点必须都不为空集.
            add(sum, mul(sub(pow2[c1], 1), sub(pow2[c3], 1)));
        }
        add(ans, sub(pow2[p.size() - 1], sum));
    }
    ans = mul(ans, pow2[n - p.size()]);
    cout << ans << '\n';

}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 3724kb

input:

3
0 0
0 1
1 0

output:

12

result:

ok 1 number(s): "12"

Test #2:

score: 0
Accepted
time: 0ms
memory: 3596kb

input:

3
0 0
0 1
0 2

output:

11

result:

ok 1 number(s): "11"

Test #3:

score: -100
Wrong Answer
time: 0ms
memory: 3600kb

input:

20
3 3
1 0
0 2
2 2
2 4
4 3
0 0
1 4
0 1
4 2
3 4
1 0
3 1
4 4
3 1
1 3
4 1
1 4
3 0
3 1

output:

4175328

result:

wrong answer 1st numbers differ - expected: '5996938', found: '4175328'