QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#726566#9520. Concave HullJustinshaoWA 29ms3936kbC++204.0kb2024-11-09 02:56:582024-11-09 02:56:59

Judging History

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

  • [2024-11-09 02:56:59]
  • 评测
  • 测评结果:WA
  • 用时:29ms
  • 内存:3936kb
  • [2024-11-09 02:56:58]
  • 提交

answer

#pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx,popcnt,sse4,abm")
#include<bits/stdc++.h>
using namespace std;
#define ZTMYACANESOCUTE ios_base::sync_with_stdio(0), cin.tie(0)
#define ll long long
#define ull unsigned long long
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define debug(x) cerr << #x << " = " << x << '\n';
#define rep(X, a, b) for(int X = a; X < b; ++X)
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pld pair<ld, ld>
#define ld long double
#define F first
#define S second

pii operator + (const pii &p1, const pii &p2) { return make_pair(p1.F + p2.F, p1.S + p2.S); }
pii operator - (const pii &p1, const pii &p2) { return make_pair(p1.F - p2.F, p1.S - p2.S); }
pll operator + (const pll &p1, const pll &p2) { return make_pair(p1.F + p2.F, p1.S + p2.S); }
pll operator - (const pll &p1, const pll &p2) { return make_pair(p1.F - p2.F, p1.S - p2.S); }

template<class T> bool chmin(T &a, T b) { return (b < a && (a = b, true)); }
template<class T> bool chmax(T &a, T b) { return (a < b && (a = b, true)); }

#define lpos pos << 1
#define rpos pos << 1 | 1
 
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << "," << p.second << ')'; }
template<typename A> ostream& operator << (ostream &os, const vector<A> &p) { for(const auto &a : p) os << a << " "; os << '\n'; return os; }
 
const int MAXN = 2e5 + 5, MOD = 998244353, IINF = 1e9 + 7, MOD2 = 1000000007;
const double eps = 1e-9;
const ll LINF = 1e18L + 5;
const int B = 320;

// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// int get_rand(int l, int r){ return uniform_int_distribution<int>(l, r)(rng); }
 
ll fpow(ll x, ll exp, ll mod = LLONG_MAX){ ll res = 1; while(exp){ if(exp & 1) res = res * x % mod; x = x * x % mod; exp >>= 1;} return res; }

#define int long long

void solve() {
    int n; cin >> n;
    vector<pll> pt(n);
    for (auto &[x, y] : pt) cin >> x >> y;
    auto cross = [&](pll a, pll b) -> ll {
        return a.F * b.S - a.S * b.F;
    };
    auto convex_hull = [&](vector<pll> &Pt) -> vector<pll> {
        sort(all(Pt));
        int N = Pt.size();
        vector<pll> hull;
        rep (i, 0, N) {
            while (hull.size() >= 2 && cross(Pt[i] - hull.end()[-2], hull.back() - hull.end()[-2]) >= 0) {
                hull.pop_back();
            }
            hull.pb(Pt[i]);
        }
        int sz = hull.size();
        for(int i = N - 2; i >= 0; --i){
            while(hull.size() > sz && cross(Pt[i] - hull.end()[-2], hull.back() - hull.end()[-2]) >= 0) hull.pop_back();
            hull.pb(Pt[i]);
        }
        hull.pop_back();
        return hull;
    };
    ll A = 0;
    auto hull = convex_hull(pt);
    int sz = hull.size();
    if (sz == n) {
        cout << -1 << '\n';
        return;
    }
    rep (i, 0, sz) A += cross(hull[i], hull[(i + 1) % sz]);
    A = abs(A);
    map<pii, int> mp;
    for (auto p : hull) mp[p] = 1;
    vector<pll> in_pt;
    rep (i, 0, n) {
        if (mp.find(pt[i]) == mp.end()) in_pt.pb(pt[i]);
    }
    auto hull2 = convex_hull(in_pt);
    int sz2 = hull2.size();
    ll sub = LINF;
    auto calc = [&](pll a, pll b, pll c) -> ll {
        return abs(cross(b - a, c - a));
    };
    auto mv = [&](int p, int d) -> int {
        p += d;
        if (p < 0) p += sz2;
        if (p >= sz2) p -= sz2;
        return p;
    };
    int ptr = 0;
    rep (i, 0, sz2) if (calc(hull[0], hull[1], hull2[i]) < calc(hull[0], hull[1], hull2[ptr])) {
        ptr = i;
    }
    rep (i, 0, sz) {
        int j = (i + 1) % sz;
        while (calc(hull[i], hull[j], hull2[ptr]) > calc(hull[i], hull[j], hull2[mv(ptr, 1)])) ptr = mv(ptr, 1);
        while (calc(hull[i], hull[j], hull2[ptr]) > calc(hull[i], hull[j], hull2[mv(ptr, -1)])) ptr = mv(ptr, -1);
        chmin(sub, calc(hull[i], hull[j], hull2[ptr]));
    }
    cout << A - sub << '\n';
}
 
main() {
    ZTMYACANESOCUTE;
    int T = 1;
    cin >> T;
    while (T--) {
        solve();
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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

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
Wrong Answer
time: 29ms
memory: 3936kb

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:

1986320445246155278
1900093336073022078
1612088392301142476
2012259136539173407
1819942017252118749
1772230185841892196
1164835025329039520
1527446155241140517
1807368432185303666
1236918659444944569
1306839249967484778
1984123720246784099
1868728080720036006
667458140583450322
2127932992585026491
4...

result:

wrong answer 16th lines differ - expected: '447172929227332597', found: '480407401379702443'