QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#796158#9520. Concave HullXiaoretaWWA 1ms3864kbC++203.9kb2024-12-01 13:28:552024-12-01 13:28:56

Judging History

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

  • [2024-12-01 13:28:56]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3864kb
  • [2024-12-01 13:28:55]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define vi vector<int>
#define rep(i,a,b) for(int i = a; i < b; ++i)
#define N 200005

double eps=1e-6;

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=1,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 getlen(){
        return sqrt(this->x*this->x+this->y*this->y);
    }

    vec normalize(){
        double x=this->x,y=this->y;
        double len=this->getlen();
        return vec(x/len,y/len);
    }

};

vec operator +(vec b,vec a){
    return vec(a.x+b.x,a.y+b.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;
        return abs(dot(c-a,t)/2.0);
    }

    double dis(point c){
        vec t=b-a;
        return abs(dot(c-a,t)/t.getlen());
    }

};

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())<eps){
            concave.pop_back();
        }
        concave.push_back(a[i]);
    }
    concave.pop_back();
    return concave;
}


void solve(){
    int n;
    cin>>n;
    vector<point> a(n);
    for(int i=0;i<n;i++){
        cin>>a[i].x>>a[i].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])continue;
        b.push_back(a[i]);
    }
    if(b.size()==0){
        cout<<-1<<'\n';
        return;
    }

    // // for(int i=0;i<b.size();i++)cout<<b[i].x<<' '<<b[i].y<<'\n';

    vector<point> smallconcave=findconcave(b);
    // // for(int i=0;i<smallconcave.size();i++){
    // //     cout<<smallconcave[i].x<<" "<<smallconcave[i].y<<'\n';
    // // }

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

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

signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    //cout<<LLONG_MAX<<'\n';
    int 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: 1ms
memory: 3836kb

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

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:

2.13087e+18
1.84702e+18
1.8239e+18
-1
2.11598e+18
-1
2.271e+18
1.99862e+18
-1
-1

result:

wrong answer 1st lines differ - expected: '2178418010787347715', found: '2.13087e+18'