Cod sursa(job #2722647)

Utilizator AndreiD31Dragan Andrei AndreiD31 Data 13 martie 2021 09:26:41
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.3 kb
#include <bits/stdc++.h>

using namespace std;

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

struct infasuratoare
{
    double x,y;
}v[120100],sol[120100];

int compare(infasuratoare A, infasuratoare B)
{
    return (
        (A.x-v[1].x)*(B.y-v[1].y) < (B.x-v[1].x)*(A.y-v[1].y)
    );
}

int viraj_dreapta(infasuratoare A, infasuratoare B, infasuratoare C)
{
    /// A.x A.y 1
    /// B.x B.y 1
    /// C.x C.y 1

    return ((A.x*B.y + B.x*C.y + A.y*C.x - B.y*C.x - C.y*A.x - B.x*A.y)>0);
}

int n,i,minix,T,punct=INT_MAX,miniy=INT_MAX;
int main()
{
    f>>n;
    for(i=1;i<=n;i++)
    {
        f>>v[i].x>>v[i].y;
        if(v[i].x<minix)
        {
            minix=v[i].x;
            miniy=v[i].y;
            punct=i;
        }
        else if(v[i].x==minix)
        {
            if(v[i].y<miniy)
            {
                miniy=v[i].y;
                punct=i;
            }
        }
    }

    swap(v[1],v[punct]);
    sort(v+2,v+n+1,compare);

    T=2;
    sol[1]=v[1];sol[2]=v[2];

    for(i=3;i<=n;i++)
    {
        while(T>=2 && viraj_dreapta(sol[T-1],sol[T],v[i]))T--;
        T++;sol[T]=v[i];
    }

    g<<T<<'\n';
    for(i=1;i<=T;i++)
        g<<fixed<<setprecision(12)<<sol[i].x<<" "<<sol[i].y<<'\n';
    return 0;
}