Cod sursa(job #2003621)

Utilizator dumitrescu_andreiDumitrescu Andrei dumitrescu_andrei Data 23 iulie 2017 14:08:26
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.49 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");

struct Punct {
float x,y,unghi;
} a[120001],S[120001];

int n,vf;

bool cmp(Punct x,Punct y)
{
    return x.unghi<y.unghi;
}

void Primul()
{
    for(int i=2;i<=n;++i)
        if(a[i].x<a[1].x)
         swap(a[i],a[1]);
        else if(a[i].x==a[1].x && a[i].y<a[1].y )
            swap(a[i],a[1]);
}

void Sortare()
{
    for(int i=2;i<=n;++i)
        a[i].unghi=atan(a[i].y/a[i].x);

    sort(a+2,a+1+n,cmp);
}

void PUSH(Punct P)
{
    vf++;
    S[vf]=P;
}

void POP()
{
    vf--;
}

float Produs(Punct P1, Punct P2,Punct P3)
{
    return (P2.x-P1.x)*(P3.y-P1.y)-(P3.x-P1.x)*(P2.y-P1.y);
}

int main()
{
    f>>n;
    for(int i=1;i<=n;++i)
        f>>a[i].x>>a[i].y;

    Primul();
    Sortare();
    vf=0;
    PUSH(a[1]);
    PUSH(a[2]);
    for(int i=3;i<=n;++i)
    {
        float o;
        o=Produs(S[vf-1],S[vf],a[i]);
        if(o==0)
        {
            POP();
            PUSH(a[i]);
        }
        else
            if(o>0)
               PUSH(a[i]);
            else
            {
                while(vf>1 && o<=0)
                {
                    POP();
                    o=Produs(S[vf-1],S[vf],a[i]);
                }
                PUSH(a[i]);
            }

    }

    g<<vf<<'\n';
    for(int i=1;i<=vf;++i)
        g<<fixed<<setprecision(6)<<S[i].x<<" "<<S[i].y<<'\n';

    return 0;

}