Cod sursa(job #2878550)

Utilizator rareshinnhoMiroiu Rares rareshinnho Data 27 martie 2022 10:43:58
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.98 kb
#include <bits/stdc++.h>

using namespace std;

ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");

struct pct
{
    double first,second;
} a[120005];

double det(pct z,pct x, pct y)
{
    return(z.first*x.second+x.first*y.second+y.first*z.second-x.second*y.first-y.second*z.first-z.second*x.first);
}

bool comp(pct x,pct y)
{
    return det(a[1],x,y)>0;
}
int n,mn;
int main()
{
    f>>n;
    f>>a[1].first>>a[1].second;
    mn=1;

    for(int i=2; i<=n; i++)
    {
        f>>a[i].first>>a[i].second;
        if(a[i].first<a[mn].first||(a[i].first==a[mn].first&&a[i].second<a[mn].second))mn=i;

    }
    swap(a[mn],a[1]);
    sort(a+2,a+n+1,comp);
    a[n+1]=a[1];
    n++;
    int l=2;
    for(int i=3; i<=n; i++)
    {
        while(l>=2&&det(a[l-1],a[l],a[i])<0)l--;
        a[++l]=a[i];
    }
    g<<l-1<<'\n';
    for(i=1; i<l; i++)
    {
        g<<fixed<<setprecision(12)<<a[i].first<<" "<<a[i].second<<'\n';
    }
    return 0;
}