Cod sursa(job #2820693)

Utilizator puica2018Puica Andrei puica2018 Data 21 decembrie 2021 11:30:44
Problema Infasuratoare convexa Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.46 kb
#include <bits/stdc++.h>
using namespace std;

ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
/// Convex HULL
struct Punct
{
    double x, y;
    bool operator < (const Punct alt) const
    {
        if(alt.y==y)
            return x<alt.x;
        return y<alt.y;
    }
};
Punct a[120003];
int n;
bool viz[120005];
int st[120005],top;
/// ret. + daca C se afla in semiplanul +
/// determinat de dreapta (A,B)
double f(Punct A, Punct B, Punct C)
{
    return (A.y - B.y)*C.x + (B.x - A.x) * C.y
     + A.x * B.y - A.y * B.x;
}

void citire()
{
    fin>>n;
    int i;
    for(i=1; i<=n; i++)
        fin>>a[i].x>>a[i].y;
}

void ConvexHull()
{
    sort(a+1,a+n+1);
    st[++top]=1;
    st[++top]=2;
    viz[2]=1;
    for(int i=3; i<=n; i++)
    {
        while(f(a[st[top-1]],a[st[top]],a[i])<0)
        {
            viz[st[top]]=0;
            top--;
        }
        st[++top]=i;
        viz[i]=1;
    }
    for(int i=n; i>=1; i--)
    {
        if(!viz[i])
        {
            while(f(a[st[top-1]],a[st[top]],a[i])<0)
                top--;
            st[++top]=i;
        }
    }
    fout<<top-1<<"\n";
    for(int i=1; i<top; i++)
        fout<<setprecision(12)<<fixed<<a[st[i]].x<<" "<<a[st[i]].y<<"\n";
}

int main()
{
    /*
    Punct A, B, C;
    A.x = A.y = 0;
    B.x = B.y = 5;
    C.x = 1; C.y = 6;
    cout << F(A,B,C);
    */
    citire();
    ConvexHull();
    return 0;
}