QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#722450#9520. Concave HullLcyanstarsWA 1ms4084kbC++142.4kb2024-11-07 19:05:072024-11-07 19:05:07

Judging History

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

  • [2024-11-07 19:05:07]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:4084kb
  • [2024-11-07 19:05:07]
  • 提交

answer

#include <bits/stdc++.h>

//jiangly, modified
using i64 = long long; // long long, double
const i64 eps=0; //0, 1e-9
struct Point {
    i64 x;
    i64 y;
    Point(i64 x = 0, i64 y = 0) : x(x), y(y) {}
    bool operator <(const Point& a) const
    {
        return x == a.x ?y<a.y:x<a.x;
    }
};

Point operator+(const Point &a, const Point &b) {
    return Point(a.x + b.x, a.y + b.y);
}

Point operator-(const Point &a, const Point &b) {
    return Point(a.x - b.x, a.y - b.y);
}

i64 dot(const Point &a, const Point &b) {
    return a.x * b.x + a.y * b.y;
}

i64 cross(const Point &a, const Point &b) {
    return a.x * b.y - a.y * b.x;
}

i64 area(const Point &a, const Point& b, const Point& c) {
    return cross(a - b, b - c); // 有向面积,正代表 b-c 在 a-b 左侧
}

std::map<Point,bool> vis;

std::vector<Point> getHull(std::vector<Point>& p) {
    std::vector<Point> h, l;
    std::sort(p.begin(), p.end());
    if (p.size() <= 1) {
        return p;
    }
    for (auto a : p) {
        while (h.size() > 1 && cross(a - h.back(), a - h[h.size() - 2]) <= eps) {
            h.pop_back();
        }
        while (l.size() > 1 && cross(a - l.back(), a - l[l.size() - 2]) >= -eps) {
            l.pop_back();
        }
        l.push_back(a);
        h.push_back(a);
    }
    l.pop_back();
    std::reverse(h.begin(), h.end());
    h.pop_back();
    l.insert(l.end(), h.begin(), h.end());
    for(auto p:l)
        vis[p]=true;
    return l;
}

int main()
{
    int _;
    for(scanf("%d",&_);_;_--)
    {
        vis.clear();
        int n;
        scanf("%d",&n);
        std::vector<Point> P(n);
        for(int i=0;i<n;i++)
            scanf("%lld%lld",&P[i].x,&P[i].y);
        auto con=getHull(P);
        std::vector<Point> nP;
        for(auto a:P)
            if(!vis[a])
                nP.push_back(a);
        auto ncon=getHull(nP);
        int N=(int)con.size(),M=(int)ncon.size();
        if(M == 0)
        {
            printf("-1\n");
            continue;
        }
        i64 ar=0;
        for(int i=0;i<N;i++)
            ar += area(con[i],con[(i+1)%N],con[(i+2)%N]);
        ar /= 2;
        i64 mn=ar;
        for(int i=0;i<N;i++)
            for(int j=0;j<M;j++)
                mn=std::min(area(con[i],con[(i+1)%N],ncon[j]),mn);
        printf("%lld\n",ar-mn);
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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

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:

436901472928748124
142985787925747604
6716882489433884
462692168984313134
592769233092856550
450587273009334171
364753001879370583
316129459382945126
750838921404253650
61161851159402348

result:

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