Cod sursa(job #1999566)

Utilizator mihneacazCazacu Mihnea mihneacaz Data 11 iulie 2017 15:23:48
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.91 kb
#include<cstdio>
#include<fstream>
#include<cmath>
#include<algorithm>
#include<stack>
#include<vector>
#define eps=0.000000000001
using namespace std;
struct POINT
{
    double x,y;
};
POINT v[120005],sol[120005];
int st[120005];
bool viz[120005];
bool cmp(POINT a,POINT b)
{
    // double m=fabs(a.x-b.x);
    if(fabs(a.y-b.y)<0.000000000001)
        return a.x<b.x;
    else
        return a.y<b.y;
}
double det(POINT a,POINT b,POINT c)
{
    return a.x*b.y+b.x*c.y+c.x*a.y-b.y*c.x-c.y*a.x-a.y*b.x;
}
int main()
{
    ifstream cin("infasuratoare.in");
    ofstream cout("infasuratoare.out");
    int n;
    cin>>n;
    for(int i=1; i<=n; ++i)
    {
        double a,b;
        cin>>a>>b;
        v[i].x=a;
        v[i].y=b;
    }
    sort(v+1,v+n+1,cmp);
    int top=0;
    POINT a,b;
    for(int i=1; i<=n; ++i)
    {

        if(top>1)
        {
            while(top>1 && det(a,b,v[i])>0)
            {
                viz[st[top]]=0;
                --top;
                a=v[st[top-1]];
                b=v[st[top]];
            }
        }
        st[++top]=i;
        viz[st[top]]=1;
        a=v[st[top-1]];
        b=v[st[top]];
    }
    int rez=0;
    for(int i=1; i<=top; ++i)
        sol[++rez]=v[st[i]];
    top=0;
    for(int i=n; i>=1; --i)
    {
        if(!viz[i])
        {
                 if(top>1)
        {
            while(top>1 && det(a,b,v[i])>0)
            {
                viz[st[top]]=0;
                --top;
                a=v[st[top-1]];
                b=v[st[top]];
            }
        }
        st[++top]=i;
        viz[st[top]]=1;
        a=v[st[top-1]];
        b=v[st[top]];
        }

    }
    for(int i=1; i<=top; ++i)
        sol[++rez]=v[st[i]];
    cout<<rez<<'\n';
    for(int i=1; i<=rez; ++i)
    {

        cout.precision(6);
        cout<<fixed<<sol[i].x<<" "<<sol[i].y<<'\n';
    }
    return 0;
}