Cod sursa(job #3270942)

Utilizator Dragos__1_1Dragos Antohi Dragos__1_1 Data 24 ianuarie 2025 21:33:13
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.32 kb
#include <bits/stdc++.h>
#define db long 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;
double det (pct a,pct b,pct c){

    return double((a.x-c.x)*(b.y-c.y)-(a.y-c.y)*(b.x-c.x));
}
bool cmp(pct a,pct b){
    return (det(a,b,v[1])>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;
    s[++cnt]=v[1];
    s[++cnt]=v[2];
    for (i=3;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;
}