Cod sursa(job #3177901)

Utilizator emazareMazare Emanuel emazare Data 30 noiembrie 2023 15:08:28
Problema Infasuratoare convexa Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.2 kb
#include <fstream>
#include <algorithm>
#include <iomanip>

using namespace std;

ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");

const int Nmax = 120005;
const long double eps = 1e-12;
int st[Nmax];
bool used[Nmax];
struct punct{
    long double x;
    long double y;
} p[Nmax];

bool cmp(punct a, punct b){
    if(a.y == b.y)
        return (a.x<b.x);
    return(a.y<b.y);
}
bool check(punct a, punct b, punct c){
    long double r = (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
    if(r<=eps)
        return 1;
    return 0;
}

int main()
{
    int n,i,k,sgn;
    fin >> n;
    for(i=1;i<=n;i++)
        fin >> p[i].x >> p[i].y;
    sort(p+1,p+n+1,cmp);
    k = 0;
    st[++k] = 1; st[++k] = 2; sgn = 1; used[1] = used[2] = 1;
    for(i=3;i>0;i+=sgn){
        if(!used[i]){
            while(k>1 && check(p[st[k-1]],p[st[k]],p[i])){
                used[st[k]] = 0;
                k--;
            }
            st[++k] = i; used[i] = 1;
        }
        if(i == n)
            sgn = -1;
    }
    fout << k << '\n';
    fout << setprecision(6) << fixed;
    for(i=1;i<=k;i++)
        fout << p[st[i]].x << " " << p[st[i]].y << '\n';
    return 0;
}