Cod sursa(job #560529)

Utilizator PopaStefanPopa Stefan PopaStefan Data 18 martie 2011 15:52:41
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 3.12 kb
#include <fstream>
#include <math.h>
#include <algorithm> //pentru sort
#define nmax 120001
#define inf 1000000001

using namespace std;

ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");

unsigned long n;

struct punct
  {
    long double x,y; //coordonatele
    long double panta; //panta fata de cel mai din stanga punct
  };

punct a[nmax]; //vectorul in care retin toate punctele
punct st[nmax]; //stiva care va contine infasuratoarea convexa

unsigned long pct=1; //indicele in vectorul a a celui mai din stanga punct
unsigned long nr; //varful stivei


struct cmp  //o structura de date care contine nu date ci o functie
{
   bool operator () (const punct &A,const punct &B)  //bool tipul pe care il intoarce ,
    {
        if(A.panta==B.panta) //daca au aceeasi panta il luam pe cel mai din exterior
            if(A.x==B.x)  //daca si x sunt egali (pe aceeasi dreapta cu pct)
                return A.y<B.y; //returneaza daca expresia este adevarata sau nu : true sau false ; daca da atunci
            else return A.x<B.x;
        else return A.panta<B.panta;
    }
};


void citire() //citresc punctele si retin pe cel mai din stanga si in caz de egalitate pe cel mai de jos
{
    fin>>n;
    unsigned int i;
    for(i=1;i<=n;i++)
    {
        fin>>a[i].x>>a[i].y;
        if(a[i].x<a[pct].x)
           pct=i;
        else if(a[i].x==a[pct].x && a[i].y<=a[pct].x)
                  pct=i;
    }

}

long double panta(long double xa,long double ya,long double xb,long double yb)
{
    if(xa==xb)
      return inf; //sa nu fie 0 la numitor
    return (yb-ya)/(xb-xa);
}



void calc_pante()
{
   unsigned int i;
   for(i=1;i<=n;i++)
     {
         a[i].panta=-inf; //daca este punctul cel mai din stanga => panta cea mai mica pt a fi primul la sortare
         if(i!=pct) //daca nu este punctul cel mai din stanga
           a[i].panta=panta(a[pct].x,a[pct].y,a[i].x,a[i].y); //calculez panta fata de pct;

     }
  sort(a+1,a+n+1,cmp()); //a+1 elementul a[1] ; a+n+1 elementul a[n] ;cmp() criteriul de comparatie
  //cmp is an optional function object that is used in place of < to perform comparisons between pairs of elements.
}

long double semn(long double x1,long double y1,long double x2,long double y2,long double x3,long double y3)
{
    return x1*y2+x2*y3+x3*y1-x3*y2-x1*y3-x2*y1;
}

void infasuratoare()
{
    unsigned long int i;
    nr=2; //varful stivei este 2
    st[1]=a[1];  //pun in stiva primele 2 numere : pct si cel cu panta cea mai mica
    st[2]=a[2];
    for(i=3;i<=n;++i)
    {
        //atata timp cat in stiva sunt mai mult de 2 elemente
        //si unghiul dinte dreptele : st[nr-1]->st[nr] si st[nr]->a[i] <=180 de grade
        while(nr>=2 && semn(st[nr-1].x,st[nr-1].y,st[nr].x,st[nr].y,a[i].x,a[i].y)<0)
            --nr;
        st[++nr]=a[i];
    }
}

void afisare()
{
    unsigned long i;
    fout<<nr<<'\n';
    for(i=1;i<=nr;i++)
      fout<<st[i].x<<" "<<st[i].y<<'\n';
}

int main()
{
    citire();
    calc_pante();
    infasuratoare();
    afisare();
    fin.close();
    fout.close();
    return 0;
}