Cod sursa(job #1372483)

Utilizator margikiMargeloiu Andrei margiki Data 4 martie 2015 13:44:16
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.63 kb
# include <fstream>
# include <algorithm>
# include <iomanip>
# define NR 120005
# define eps 1e-12
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
struct elem
{
    double x, y;
}E, a[NR];
bool cmp (elem a, elem b)
{
    if (a.x>=b.x) return 0;
    else if (a.x==b.x && a.y>=b.y) return 0;
    else return 1;
}
int i,j,n,m,h,next;
int luat[NR], st[NR];
inline int cmp1(double a, double b)
{
    if (a+eps<b) return 1;
    if (b+eps<a) return -1;
    return 0;
}
int semn(elem a, elem b, elem c)
{
    double A,B,C;
    A = a.y-b.y;
    B = b.x-a.x;
    C = a.x*b.y - b.x*a.y;
    return cmp1(A*c.x+B*c.y+C,0);
}
void rezolva()
{
    int k,sens;
    sort (a+1, a+n+1, cmp);

    st[1]=1; st[2]=2; luat[2]=1;
    k=2; next=3; sens=1;

    while (! luat[1]) // nu s-a inchis poligonul convex
    {
        while (luat[next]) // se cauta un punct neutilizat inca pe infasuratoare
        {
            if (next==n) sens=-1;
            next+=sens;
        }
        while (k>=2 && semn(a[st[k-1]], a[st[k]], a[next])==-1) //verificare daca punctul respecta proprietatea prin functia "semn"
        {
            luat[st[k--]]=0; //scoatere din stiva
        }

        st[++k]=next; //introducerea punctului valid in stiva
        luat[next]=1;
    }
    h=k-1; // h=nr de puncte de pe infasuratoare
}
int main ()
{
    f>>n;
    for (i=1; i<=n; ++i)
        f>>a[i].x>>a[i].y;

    rezolva();

    g<<h<<"\n";
    for (i=h+1; i>1; --i)
         g<<fixed<<setprecision(6)<<a[st[i]].x<<" "<<a[st[i]].y<<"\n"; // punctele de pe infasuratoare

    return 0;
}