QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#730688#9520. Concave Hullsilver_museWA 2ms9800kbC++202.7kb2024-11-09 21:03:562024-11-09 21:03:57

Judging History

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

  • [2024-11-09 21:03:57]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:9800kb
  • [2024-11-09 21:03:56]
  • 提交

answer

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define ph push_back
#define pp pop_back
using namespace std;

typedef int db;
// const double eps=1e-8;
// int sgn(db x)
// {
//     if(fabs(x)<eps) return 0;
//     else return x<0?-1:1;
// }
struct Point
{
    db x,y;
    Point(){}
    Point(db x,db 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 ==(Point B){ return x-B.x==0&&y-B.y==0; }
    bool operator <(Point B)
    {
        return (x-B.x<0)||(x-B.x==0&&y-B.y<0);
    }
};
typedef Point Vector;
double cross(Vector A,Vector B){ return A.x*B.y-A.y*B.x; }
double dist(Point A,Point B){ return hypot(A.x-B.x,A.y-B.y); }
int convexhull(Point *p,int n,Point *ch)
{
    sort(p,p+n);
    int v=0;
    for(int i=0;i<n;i++)
    {
        while(v>1&&cross(ch[v-1]-ch[v-2],p[i]-ch[v-1])<=0) v--;
        ch[v++]=p[i];
    }
    int j=v;
    for(int i=n-2;i>=0;i--)
    {
        while(v>j&&cross(ch[v-1]-ch[v-2],p[i]-ch[v-1])<=0) v--;
        ch[v++]=p[i];
    }
    if(n>1) v--;
    return v;
}
int area(Point a,Point b,Point c)
{
    return abs(cross(b-a,c-a));
}

const int N=2e5+5,inf=8e18;
int T,n;
Point p[N],pi[N],cho[N],chi[N];
set<pair<int,int> >mp;

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin>>T;
    while(T--)
    {
        cin>>n;
        for(int i=0;i<n;i++) cin>>p[i].x>>p[i].y;
        int cnto=convexhull(p,n,cho);
        mp.clear();
        for(int i=0;i<cnto;i++) mp.insert(make_pair(cho[i].x,cho[i].y));
        int ni=0;
        for(int i=0;i<n;i++)
            if(!mp.count(make_pair(p[i].x,p[i].y))) pi[ni++]=p[i];
        if(!ni) { cout<<-1<<endl; continue; }
        int res=0,mn=inf;
        for(int i=0;i<cnto;i++) res+=area(cho[i],pi[0],cho[(i+1)%cnto]);
        if(ni<3)
        {
            for(int i=0;i<cnto;i++)
            {
                Point u=cho[i],v=cho[(i+1)%cnto];
                for(int j=0;j<ni;j++)
                    mn=min(mn,area(u,v,pi[j]));
            }
        }
        else
        {
            int cnti=convexhull(pi,ni,chi);
            int t=0;
            for(int i=0;i<cnti;i++)
                if(area(cho[0],cho[1],chi[i])<area(cho[0],cho[1],chi[t]))
                    t=i;
            for(int i=0;i<cnto;i++)
            {
                Point u=cho[i],v=cho[(i+1)%cnto];
                while(area(u,v,chi[t])>=area(u,v,chi[(t+1)%cnti])) t=(t+1)%cnti;                
                mn=min(mn,area(u,v,chi[t]));
            }
        }
        cout<<res-mn<<endl;
    }
    return 0;
}
/*
2
6
-2 0
1 -2
5 2 
0 4
1 2
3 1
4
0 0
1 0
0 1
1 1
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 9776kb

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: 0ms
memory: 9800kb

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:

2178418010787347700
1826413114144932131
1651687576234220000
1883871859778998988
2119126281997959876
894016174881844599
2271191316922158930
1998643358049669477
1740474221286618688
1168195646932543182

result:

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