QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#791945#9520. Concave Hullticking_awayWA 1ms3880kbC++203.5kb2024-11-28 22:14:152024-11-28 22:14:23

Judging History

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

  • [2024-11-28 22:14:23]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3880kb
  • [2024-11-28 22:14:15]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
using ui = unsigned int;
using ull = unsigned long long;
using ll = long long;
#define endl '\n'
using pii = pair<int, int>;
using pll = pair<ll, ll>;
const int maxn = 2e5 + 10;
const int mod = 1000000007;
#define inl inline
#define fr(i, a, b) for (int i = a; i <= b; i++)
#define ford(i, a, b) for (int i = a; i >= b; i--)
#define forall(i, a) for (auto &i : a)

/**
   ____         ___ _____
  / ___| _   _ / _ \___ /
  \___ \| | | | | | ||_ \
   ___) | |_| | |_| |__) |
  |____/ \__, |\___/____/
         |___/
*/
istream &operator>>(istream &in, vector<int> &v)
{
    for (auto &i : v)
        in >> i;
    return in;
}
ostream &operator<<(ostream &out, vector<int> &v)
{
    for (auto &i : v)
        out << i << " ";
    return out;
}
bool _output = 1;

const int EPS = 0;
inline int sign(int a)
{
    return a < -EPS ? -1 : a > EPS;
}

inline int cmp(int a, int b)
{
    return sign(a - b);
}

#define int ll
struct Point
{
    int x, y;
    Point() {}
    Point(int _x, int _y) : x(_x), y(_y) {}
    Point operator-(Point &b)
    {
        return Point(x - b.x, y - b.y);
    }
    Point operator+(Point &b)
    {
        return Point(x + b.x, y + b.y);
    }
    bool operator<(const Point &b) const
    {
        return x < b.x || (x == b.x && y < b.y);
    }
};
int det(Point a, Point b)
{
    return a.x * b.y - a.y * b.x;
}
bool to_left(Point a, Point b, Point c)
{
    return det(b - a, c - a) > 0;
}

#define cross(p1, p2, p3) \
    ((p2.x - p1.x) * (p3.y - p1.y) - (p3.x - p1.x) * (p2.y - p1.y))
#define crossOp(p1, p2, p3) sign(cross(p1, p2, p3))
vector<Point> convexHull(vector<Point> ps)
{
    int n = ps.size();
    if (n <= 2)
        return ps;
    sort(ps.begin(), ps.end());
    vector<Point> qs(n * 2);
    int k = 0;
    for (int i = 0; i < n; qs[k++] = ps[i++])
        while (k > 1 && crossOp(qs[k - 2], qs[k - 1], ps[i]) <= 0)
            --k;
    for (int i = n - 2, t = k; i >= 0; qs[k++] = ps[i--])
        while (k > t && crossOp(qs[k - 2], qs[k - 1], ps[i]) <= 0)
            --k;
    qs.resize(k - 1);
    return qs;
}
void solve()
{
    int n;
    cin >> n;
    vector<Point> a;
    fr(i, 1, n)
    {
        int x, y;
        cin >> x >> y;
        a.push_back(Point(x, y));
    }

    auto c1 = convexHull(a);
    set<Point> st;
    for (auto i : c1)
    {
        st.insert(i);
    }
    vector<Point> b;
    for (auto v : a)
    {
        if (!st.count(v))
        {
            b.push_back(v);
        }
    }
    // cout << b.size() << endl;
    if (b.size() == 0)
    {
        cout << -1 << endl;
        return;
    }
    auto c2 = convexHull(b);
    int sz1 = c1.size(), sz2 = c2.size();
    int j = 0;
    auto cal = [&](Point &a, Point &b, Point &c)
    {
        return abs(det(b - a, c - a));
    };
    int ans = 1e18;
    for (int i = 0; i < sz1; i++)
    {
        while (cal(c1[i], c1[(i + 1) % sz1], c2[j]) > cal(c1[i], c1[(i + 1) % sz1], c2[(j + 1) % sz2]))
        {
            j = (j + 1) % sz2;
        }
        ans = min(ans, cal(c1[i], c1[(i + 1) % sz1], c2[j]));
    }
    int area = 0;
    for (int i = 0; i < sz1; i++)
    {
        area += det(c1[i], c1[(i + 1) % sz1]);
    }
    ans = area - ans;
    cout << ans << endl;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int _ = 1;
    if (_output)
        cin >> _;
    while (_--)
        solve();
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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

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:

202795276562761961
-905211802639263098
253210827344392389
-788416674058499283
-858965342288099898
335194309462221745
16942755278123180
-447935083750505833
-733729900579454325
-183304553600668513

result:

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