QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#726397#9520. Concave HullRWeakestTL 1ms3628kbC++173.7kb2024-11-08 23:45:502024-11-08 23:45:50

Judging History

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

  • [2024-11-08 23:45:50]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:3628kb
  • [2024-11-08 23:45:50]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;
#define ll long long

const int N = 2e5 + 10;

ll Test, n, m, k;

struct point {
    ll x, y;

    point(ll x_ = 0, ll y_ = 0) : x(x_), y(y_) {}

    point &operator+=(point p) &{ return x += p.x, y += p.y, *this; }

    point &operator+=(ll t) &{ return x += t, y += t, *this; }

    point &operator-=(point p) &{ return x -= p.x, y -= p.y, *this; }

    point &operator-=(ll t) &{ return x -= t, y -= t, *this; }

    point &operator*=(ll t) &{ return x *= t, y *= t, *this; }

    point &operator/=(ll t) &{ return x /= t, y /= t, *this; }

    friend point operator+(point a, point b) { return a += b; }

    friend point operator+(point a, ll b) { return a += b; }

    friend point operator-(point a, point b) { return a -= b; }

};

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

ll cross(point p1, point p2, point p3) {
    return cross(p2 - p1, p3 - p2);
}

bool cmp(point a, point b) {
    if (a.y != b.y) return a.y < b.y;
    return a.x < b.x;
}

point basep;

bool cmpangle(point a, point b) {
    if ((a.x - basep.x) * (b.y - basep.y) != (a.y - basep.y) * (b.x - basep.x))
        return (a.x - basep.x) * (b.y - basep.y) > (a.y - basep.y) * (b.x - basep.x);
    return (abs(a.x - basep.x) + abs(a.y - basep.y) < abs(b.x - basep.x) + abs(b.y - basep.y));
}

vector<point> p, con1, con2;

pair<vector<point>, vector<point> > convex(vector<point> v) {
    vector<point> con, res;
    if (v.size() <= 2) return make_pair(v, res);
    basep = v[0];
    for (int i = 1; i < v.size(); i++)
        if (v[i].y < basep.y) basep = v[i];
    sort(v.begin(), v.end(), cmpangle);

    con.push_back(v[0]);
    for (int i = 1; i < v.size(); i++) {
        while (con.size() > 1 && cross(con[con.size() - 2], con[con.size() - 1], v[i]) < 0) {
            res.push_back(con[con.size() - 1]);
            con.pop_back();
        }
        con.push_back(v[i]);
    }

//    for (int i = 0; i < v.size(); i++) printf("%d:  (%lld,%lld)\n", i, v[i].x, v[i].y);
//    printf("convex\n");
//    for (int i = 0; i < con.size(); i++) printf("%d:  (%lld,%lld)\n", i, con[i].x, con[i].y);
//    printf("res\n");
//    for (int i = 0; i < res.size(); i++) printf("%d:  (%lld,%lld)\n", i, res[i].x, res[i].y);

    return make_pair(con, res);
}

ll area(point a, point b, point c) {
    return abs(cross(a, b, c));
}

ll area(vector<point> v) {
    ll res = 0;
    for (int i = 1; i < v.size() - 1; i++) {
        res += area(v[0], v[i], v[i + 1]);
    }
    return res;
}

void solve() {
    cin >> n;
    p.clear(), con1.clear(), con2.clear();
    for (int i = 1; i <= n; i++) {
        ll x, y;
        cin >> x >> y;
        p.emplace_back(x, y);
    }

    pair<vector<point>, vector<point> > result = convex(p);
    if (result.first.size() == n) {
        cout << "-1\n";
        return;
    }
    con1 = result.first;
    p = result.second;
    con2 = convex(p).first;

    ll sum = area(con1), mini = 4e18;

    int j = 0;
    for (int i = 0; i < con1.size(); i++) {
        point a = con1[i], b = con1[(i + 1) % con1.size()];
        while (area(a, b, con2[(j + 1) % con2.size()]) <= area(a, b, con2[j])) {
            mini = min(mini, area(a, b, con2[j]));
            j = (j + 1) % con2.size();
        }
        mini = min(mini, area(a, b, con2[j]));
    }


    cout << sum - mini << "\n";
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr), std::cout.tie(nullptr);

    cin >> Test;
    while (Test--) {
        solve();
    }


    return 0;
}

/*
 2
 6
 -2 0
 1 -2
 5 2
 0 4
 1 2
 3 1
 4
 0 0
 1 0
 0 1
 1 1
 */

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3548kb

input:

2
6
-2 0
1 -2
5 2
0 4
1 2
3 1
4
0 0
1 0
0 1
1 1

output:

40
-1

result:

ok 2 lines

Test #2:

score: 0
Accepted
time: 1ms
memory: 3628kb

input:

10
243
-494423502 -591557038
-493438474 -648991734
-493289308 -656152126
-491185085 -661710614
-489063449 -666925265
-464265894 -709944049
-447472922 -737242534
-415977509 -773788538
-394263365 -797285016
-382728841 -807396819
-373481975 -814685302
-368242265 -818267002
-344482838 -833805545
-279398...

output:

2178418010787347715
1826413114144932145
1651687576234220014
1883871859778998985
2119126281997959892
894016174881844630
2271191316922158910
1998643358049669416
1740474221286618711
1168195646932543192

result:

ok 10 lines

Test #3:

score: -100
Time Limit Exceeded

input:

1000
125
64661186 -13143076
302828013 -185438065
-418713797 -191594241
430218126 -397441626
354327250 -836704374
149668812 -598584998
311305970 66790541
199720625 -592356787
468137 -584752683
258775829 96211747
-358669612 -134890109
-129221188 -998432368
-277309896 -140056561
356901185 420557649
-51...

output:


result: