QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#735934#9520. Concave HullPHarrWA 1ms3832kbC++203.0kb2024-11-11 22:53:082024-11-11 22:53:08

Judging History

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

  • [2024-11-11 22:53:08]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3832kb
  • [2024-11-11 22:53:08]
  • 提交

answer

#include <bits/stdc++.h>

using i32 = int32_t;
using i64 = long long;

#define int i64

const int inf = LLONG_MAX / 2;

struct Point {
    i64 x, y;

    Point(i64 x = 0, i64 y = 0) : x(x), y(y) {};
};

const Point O(0, 0);

using Vec = Point;
using Points = std::vector<Point>;

Vec operator-(Vec u, Vec v) { return Vec(u.x - v.x, u.y - v.y); }

int operator^(Vec u, Vec v) { return u.x * v.y - u.y * v.x; }

bool operator<(Point A, Point B) {
    if (A.x != B.x) return A.x < B.x;
    return A.y < B.y;
}


bool check(Point p, Point q, Point r) {
    return 0 < ((q - p) ^ (r - q));
}

std::pair<Points, Points> chull(Points &ps) {
    std::sort(ps.begin(), ps.end());
    std::vector<int> I{0}, used(ps.size());

    for (int i = 1; i < ps.size(); i++) {
        while (I.size() > 1 and !check(ps[I[I.size() - 2]], ps[I.back()], ps[i]))
            used[I.back()] = 0, I.pop_back();
        used[i] = 1, I.push_back(i);
    }
    for (int i = ps.size() - 2, tmp = I.size(); i >= 0; i--) {
        if (used[i]) continue;
        while (I.size() > tmp and !check(ps[I[I.size() - 2]], ps[I.back()], ps[i]))
            used[I.back()] = 0, I.pop_back();
        used[i] = 1, I.push_back(i);
    }
    Points H;
    I.pop_back();
    for (auto i: I)
        H.push_back(ps[i]);

    Points notH;
    for (int i = 1; i < ps.size(); i++) {
        if (used[i]) continue;
        notH.push_back(ps[i]);
    }
    return std::pair(H, notH);
}

int area(Point a, Point b, Point c) {
    return abs((b - a) ^ (c - a));
}

void solve() {
    int n;
    std::cin >> n;
    Points ps(n);

    for (auto &[x, y]: ps)
        std::cin >> x >> y;

    auto [c1, new_ps] = chull(ps);
    ps = move(new_ps);
    int chull_area = 0;
    for (int i = 0; i < c1.size(); i++)
        chull_area += c1[i] ^ c1[(i + 1) % c1.size()];

    if (ps.empty()) {
        std::cout << -1 << "\n";
    } else if (ps.size() < 3) {
        int ret = inf;
        for (int i = 0; i < ps.size(); i++)
            for (int j = 0; j < c1.size(); j++)
                ret = std::min(ret, area(ps[i], c1[j], c1[(j + 1) % c1.size()]));
        std::cout << chull_area - ret << "\n";
    } else {
        auto [c2, _] = chull(ps);
        int it = 0, val = abs((c1[0] - c2[0]) ^ (c1[1] - c2[0]));
        for (int i = 1, x; i < c1.size(); i++) {
            x = abs((c1[i] - c2[0]) ^ (c1[(i + 1) % c1.size()] - c2[0]));
            if (x < val) val = x, it = i;
        }
        int ret = val;
        for (int i = 1; i < c2.size(); i++) {
            val = area(c2[i], c1[it], c1[(it + 1) % c1.size()]);
            for (int x; true; it = (it + 1) % c1.size()) {
                x = area(c2[i], c1[(it + 1) % c1.size()], c1[(it + 2) % c1.size()]);
                if (x < val) break;
                val = x;
            }
            ret = std::min(ret, val);
        }
        std::cout << chull_area - ret << "\n";
    }
    return;
}

i32 main() {
    i32 T;
    std::cin >> T;
    while (T--)
        solve();
    return 0;
}

详细

Test #1:

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

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: -100
Wrong Answer
time: 1ms
memory: 3624kb

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:

2178418249423475482
1826492460023382989
1651697692844645214
1886839869418844066
2119199302041136871
900467824702762240
2271195393889053195
1998645723761517330
1754203566236599881
1170294543139875761

result:

wrong answer 1st lines differ - expected: '2178418010787347715', found: '2178418249423475482'