QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#796202#9520. Concave HullincloudWA 1ms3664kbC++143.6kb2024-12-01 14:09:392024-12-01 14:09:41

Judging History

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

  • [2024-12-01 14:09:41]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3664kb
  • [2024-12-01 14:09:39]
  • 提交

answer

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

#define ll __int128_t
#define int ll
#define N 200005
#define double ll



class point{
public:
    double x;
    double y;
    int id;
    point(){
        x=0;y=0;
        id=0;
    }
    point(int x,int y){
        this->x=x;
        this->y=y;
        id=0;
    }

    bool operator <(const point& b)const{
        if(this->x==b.x)return this->y<b.y;
        else return this->x<b.x;
    }
};


class vec{
public:
    double x,y;
    vec(){
        this->x=0,this->y=0;
    }

    vec(point a,point b){
        x=b.x-a.x;
        y=b.y-a.y;
    }

    vec(double x,double y){
        this->x=x;
        this->y=y;
    }
};

double dot(vec a,vec b){
    return a.x*b.y-a.y*b.x;
}

double across(vec a,vec b){
    return a.x*b.x+b.y*b.y;
}

vec operator -(point a,point b){
    return vec(b,a);  
}

class line{
public:
    point a;
    point b;
    line (point a,point b){
        this->a=a;
        this->b=b;
    }

    double area(point c){
        vec t=b-a;
        int ans=dot(c-a,t);
        if(ans<0)return -ans;
        return ans;
    }

};

bool del[N];
point povit;
bool cmp(point& a,point& b){
    vec ta=a-povit,tb=b-povit;
    return ta.y*tb.x<tb.y*ta.x;
}


vector<point> findconcave(vector<point> a){
    if(a.size()<=2)return a;
    sort(a.begin(),a.end());
    povit=a[0]; 
    sort(a.begin(),a.end(),cmp);
    // for(int i=0;i<a.size();i++)cout<<a[i].x<<" "<<a[i].y<<'\n';
    // cout<<'\n';
    vector<point> concave;
    concave.push_back(a[0]);
    concave.push_back(a[1]);
    a.push_back(a[0]);
    for(int i=2;i<a.size();i++){
        while(concave.size()>=2&&dot(concave.back()-concave[concave.size()-2],a[i]-concave.back())<0){
            concave.pop_back();
        }
        concave.push_back(a[i]);
    }
    concave.pop_back();
    return concave;
}


void solve(){
    signed n;
    cin>>n;
    vector<point> a(n);
    for(int i=0;i<n;i++){
        signed x,y;
        cin>>x>>y;
        a[i].x=x;
        a[i].y=y;
        a[i].id=i;
    }

    vector<point> bigconcave=findconcave(a);
    for(int i=0;i<bigconcave.size();i++){
        //cout<<bigconcave[i].x<<' '<<bigconcave[i].y<<'\n';
        del[bigconcave[i].id]=true;
    }

    double ans=0;
    for(int i=1;i+1<bigconcave.size();i++){
        line t(bigconcave[i+1],bigconcave[i]);
        ans+=t.area(bigconcave[0]);
    }

    

    vector<point> b; 
    for(int i=0;i<n;i++){
        if(del[i])del[i]=false;
        else b.push_back(a[i]);
    }
    if(b.size()==0){
        cout<<-1<<'\n';
        return;
    }


    vector<point> smallconcave=findconcave(b);


    int m=smallconcave.size();
    bigconcave.push_back(bigconcave[0]);

    int minp;
    double min_area=LLONG_MAX;

    line baseline(bigconcave[0],bigconcave[1]);
    for(int i=0;i<m;i++){
        double area=baseline.area(smallconcave[i]);
        if(area<min_area){
            min_area=area;
            minp=i;
        }
    }
    double minarea=LLONG_MAX;
    int cur=minp;
    for(int i=0;i+1<bigconcave.size();i++){
        line t(bigconcave[i],bigconcave[i+1]);
        while(t.area(smallconcave[cur])>t.area(smallconcave[(cur+1)%m])){
            cur++;
            cur%=m;
        }
        minarea=min(minarea,t.area(smallconcave[cur]));
    }

    cout<<(long long)(ans-minarea)<<'\n';
}

signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    //cout<<LLONG_MAX<<'\n';
    signed tt=1;
    cin>>tt;
    while(tt--)solve();
    
    return 0;    
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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

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:

2130866400827633371
1847065671162674296
1823982744534958390
2159586671793974985
2117824330996691672
894016174881844630
2271001696936895728
1998625041639717604
1740474221286618711
1168307634951911847

result:

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