Cod sursa(job #1109315)

Utilizator nalexandruIovan Alexandru Nicolae nalexandru Data 16 februarie 2014 23:05:29
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.6 kb
#include <fstream>
#include <cmath>
#define NMax 101

using namespace std;

fstream fin("infasuratoare.in",ios::in);
fstream fout("infasuratoare.out",ios::out);

struct Punct{float x,y;};

Punct Pcts[NMax],stiva[NMax],Min;
int n,varf;

void Citire()
{
    fin>>n;
    for(int i=0;i<n;i++)
        fin>>Pcts[i].x>>Pcts[i].y;
}

int StangaJos()
{
    int pct=0;
    for(int i=1;i<n;i++)
    {
        if(Pcts[i].y<Pcts[pct].y)
            pct=i;
        else if(Pcts[i].y==Pcts[pct].y&&Pcts[i].x<Pcts[pct].x)
            pct=i;
    }

    return pct;
}

int Cadran(int x, int y)
{
    if(x>=0&&y>=0) return 0;
    if(x<0) return 1;
    if(x>=0&&y<0) return 2;
}

void QuickSort(int st,int dr)
{
    int i,j;
    double xtan;
    Punct X;
    if(st<dr)
    {
        X=Pcts[st];i=st;j=dr;

        xtan=atan((X.y-Pcts[0].y)/(X.x-Pcts[0].x))+M_PI*Cadran(X.x-Pcts[0].x,X.y-Pcts[0].y);
        while(i<j)
        {
            while( i<j && (atan( (Pcts[j].y-Pcts[0].y) / (Pcts[j].x-Pcts[0].x) )+M_PI*Cadran(Pcts[j].x-Pcts[0].x,Pcts[j].y-Pcts[0].y) )>=xtan )  j--;
            Pcts[i]=Pcts[j];
            while( i<j && (atan( (Pcts[i].y-Pcts[0].y) / (Pcts[i].x-Pcts[0].x) )+M_PI*Cadran(Pcts[i].x-Pcts[0].x,Pcts[i].y-Pcts[0].y) )<=xtan)  i++;
            Pcts[j]=Pcts[i];
        }
        Pcts[i]=X;
        QuickSort(st,i-1);
        QuickSort(i+1,dr);
    }
}

void PUSH(Punct P)
{
    stiva[++varf]=P;
}

void POP()
{
    varf--;
}

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

void ScanareaGraham()
{
    int pct,i,prod;
    pct=StangaJos();
    swap(Pcts[0],Pcts[pct]);
    QuickSort(1,n-1);

    varf=-1;
    PUSH(Pcts[0]); PUSH(Pcts[1]);
    for(i=2;i<n;i++)
    {
        prod=Produs(stiva[varf-1],stiva[varf],Pcts[i]);
        if(prod==0)//coliniare
        //elimin stiva[varf] si pun in loc P[i]
        {
            POP();
            PUSH(Pcts[i]);
        }
        else if(prod>0) PUSH(Pcts[i]);//la stanga
                else//prod<0
                {
                POP();
                while(Produs(stiva[varf-1],stiva[varf],Pcts[i])<0&&varf>0) POP();
                PUSH(Pcts[i]);
                }
    }

}

void Tipar()
{
    //for(int i=0;i<n;i++)
       // fout<<"P["<<i<<"]("<<Pcts[i].x<<","<<Pcts[i].y<<"): "<<atan( (Pcts[i].y-Pcts[0].y)/(Pcts[i].x-Pcts[0].x) )<<endl;
    fout<<varf+1;
    for(int i=0;i<=varf;i++)
        fout<<stiva[i].x<<" "<<stiva[i].y<<endl;
}



int main()
{
    Citire();
    ScanareaGraham();
    Tipar();

    return 0;
}