QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#796184#9520. Concave HullincloudCompile Error//C++143.6kb2024-12-01 13:55:512024-12-01 13:55:51

Judging History

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

  • [2024-12-01 13:55:51]
  • 评测
  • [2024-12-01 13:55:51]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#include<conio.h>
#define ll long long
#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 getlen(){
        return sqrt(this->x*this->x+this->y*this->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));
    }

};

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(){
    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])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<<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

answer.code:3:9: fatal error: conio.h: No such file or directory
    3 | #include<conio.h>
      |         ^~~~~~~~~
compilation terminated.