Cod sursa(job #3270413)

Utilizator Dragos__1_1Dragos Antohi Dragos__1_1 Data 23 ianuarie 2025 12:49:19
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.3 kb
#include <bits/stdc++.h>
#define db double
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
struct pct{
    db x;
    db y;
    bool operator == (pct b){
        if (x==b.x&&y==b.y)return 1;
    }
    void operator = (pct b){
        x=b.x;
        y=b.y;
    }
}v[120004],*p0,s[120004];
long long n,i,j,cnt;
db det (pct a,pct b,pct c){
    a.x-=c.x;
    b.x-=c.x;
    a.y-=c.y;
    b.y-=c.y;
    return double(b.x*a.y-b.y*a.x);
}
bool cmp(pct a,pct b){
    return (det(a,b,*p0)<0);
}
int main()
{   f>>n;
    for(i=1;i<=n;i++){
        f>>v[i].x>>v[i].y;
        if (i==1)p0=&v[i];
        if (v[i].y<(*p0).y){
            p0=&v[i];
        }
        if (v[i].y==(*p0).y&&(*p0).x<v[i].x){
            p0=&v[i];
        }
    }
    swap(*p0,v[1]);
    sort(v+2,v+n+1,cmp);
    //for (i=1;i<=n;i++){
    //    cout<<v[i].x<<' '<<v[i].y<<'\n';
    //}
    v[n+1]=*p0;
    for (i=1;i<=n+1;i++){
        while (cnt>=2){
            db aux=det(v[i],s[cnt],s[cnt-1]);
            if (aux<0)cnt--;
            else break;
        }
        s[++cnt]=v[i];
    }
    cnt--;
    g<<cnt<<'\n';
    for (i=1;i<=cnt;i++){
        g<<fixed<<setprecision(12)<<s[i].x<< ' ' <<s[i].y<<'\n';
    }
    //cout<<det({1,3},{3,1},{0,0});
    return 0;
}