QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#726509#9520. Concave HullExtractStarsWA 1ms3808kbC++173.6kb2024-11-09 01:53:362024-11-09 01:53:36

Judging History

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

  • [2024-11-09 01:53:36]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3808kb
  • [2024-11-09 01:53:36]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ld = long double;

struct Point
{
    ll x, y;
    bool operator<(const Point &rhs) const
    {
        return (x < rhs.x) || (x == rhs.x && y < rhs.y);
    }
};

ll cross(const Point &O, const Point &A, const Point &B)
{
    return (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x);
}

vector<Point> convexHull(vector<Point> &pts)
{
    int n = pts.size();
    sort(pts.begin(), pts.end());

    vector<Point> hull;

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

    int t = hull.size() + 1;
    for (int i = n - 2; i >= 0; --i)
    {
        while (hull.size() >= t && cross(hull[hull.size() - 2], hull[hull.size() - 1], pts[i]) <= 0)
        {
            hull.pop_back();
        }
        hull.push_back(pts[i]);
    }

    hull.pop_back();

    return hull;
}

ll area2(const vector<Point> &p)
{
    ll area2 = 0;
    int n = p.size();
    for (int i = 0; i < n; ++i)
    {
        int j = (i + 1) % n;
        area2 += (p[i].x * p[j].y) - (p[j].x * p[i].y);
    }
    return abs(area2);
}

ll dis2(const Point &a, const Point &b)
{
    ll dx = a.x - b.x;
    ll dy = a.y - b.y;
    return dx * dx + dy * dy;
}
void solve()
{
    int n;
    cin >> n;
    vector<Point> P(n);
    for (int i = 0; i < n; ++i)
    {
        cin >> P[i].x >> P[i].y;
    }
    vector<Point> poly = convexHull(P);
    int num = poly.size();
    if (num == n)
    {
        cout << "-1\n";
        return;
    }
    ll S = area2(poly);

    vector<pair<ll, ll>> temp;
    for (auto &p : poly)
    {
        temp.emplace_back(p.x, p.y);
    }
    sort(temp.begin(), temp.end());

    vector<Point> waitP;
    for (int i = 0; i < n; ++i)
    {
        pair<ll, ll> t = {P[i].x, P[i].y};
        if (!binary_search(temp.begin(), temp.end(), t))
        {
            waitP.push_back(P[i]);
        }
    }

    if (waitP.empty())
    {
        cout << "1\n";
        return;
    }

    ll tot = 0;
    for (int i = 0; i < num; ++i)
    {
        int j = (i + 1) % num;
        tot += (poly[i].x * poly[j].y) - (poly[j].x * poly[i].y);
    }
    if (tot < 0)
    {
        reverse(poly.begin(), poly.end());
    }

    auto area = [&](const Point &a, const Point &b, const Point &x) -> ll
    {
        ll s = (b.x - a.x) * (x.y - a.y) - (b.y - a.y) * (x.x - a.x);
        return abs(s);
    };

    ll mn = 1e18;

    for (auto &x : waitP)
    {
        int l = 0;
        int r = num - 1;
        while (r - l > 4)
        {
            int m1 = l + (r - l) / 3;
            int m2 = r - (r - l) / 3;
            ll cross1 = area(poly[m1], poly[(m1 + 1) % num], x);
            ll cross2 = area(poly[m2], poly[(m2 + 1) % num], x);
            if (cross1 < cross2)
                r = m2;
            else
                l = m1;
        }
        ll temp = 1e18;
        for (int i = l; i <= r; ++i)
        {
            ll cur = area(poly[i], poly[(i + 1) % num], x);
            if (cur < temp)
                temp = cur;
        }
        if (temp < mn)
            mn = temp;
    }

    ll ans = S - mn;
    if (ans > 0)
        cout << ans << "\n";
    else
        cout << "-1\n";
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    int _;
    cin >> _;
    while (_--)
    {
        solve();
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 3640kb

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:

2178410906926518141
1826413114144932145
1651687576234220014
1883871859778998985
2117861879018439740
894016174881844630
2271174337159857750
1998643358049669416
1727300161677395529
1168195646932543192

result:

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