Cod sursa(job #1046326)

Utilizator nod_softwareBudisteanu Ionut Alexandru nod_software Data 2 decembrie 2013 20:35:04
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 4.78 kb
#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

const int _iMaxNumber = 120001;

class TPoint
{
   public:
      double fSlope;
      double fX, fY;
      TPoint(double fNewValue, double fNewValueY);

      void ComputeSlope(TPoint * ptOther);
      bool operator<(const TPoint& ptOther);
      bool operator>(const TPoint& ptOther);
   protected:
};

class TConvexHull
{
   public:
      TConvexHull();
      TPoint * m_vHull[_iMaxNumber];
      int m_iHullLength;

      TPoint * ptMinimum;
      double CheckPoint(const TPoint* ptA, const TPoint* ptB, const TPoint* ptC) ;

      void AddPoint(double fX, double fY);
      void Solve();
   private:
      void ComputeSlopes();
   protected:

      TPoint * m_vPoints[_iMaxNumber];
      int m_iPointsLength;

} * objHull;

//------------------------------------------------
TPoint::TPoint(double fNewValueX, double fNewValueY)
{
   this->fX=fNewValueX;
   this->fY=fNewValueY;
}
//------------------------------------------------
void TPoint::ComputeSlope(TPoint * ptOther)
{
   if (this->fX-ptOther->fY == 0)
      this->fSlope=0;
   else
      this->fSlope=(this->fY-ptOther->fY)/(this->fX-ptOther->fY);
}
//------------------------------------------------
bool TPoint::operator<(const TPoint & ptOther)
{
   //return  (this>ptOther);
}
//------------------------------------------------
bool TPoint::operator>(const TPoint & ptOther)
{
   if ((this->fX>ptOther.fX)||((this->fX==ptOther.fX)&&(this->fY>ptOther.fY)))
      return true;
   else
      return false;
}
//------------------------------------------------
//------------------------------------------------
//------------------------------------------------
void TConvexHull::AddPoint(double fX, double fY)
{
   this->m_iPointsLength++;

   m_vPoints[m_iPointsLength]=new TPoint(fX, fY);

   if (this->m_iPointsLength==1)
      this->ptMinimum=m_vPoints[m_iPointsLength];
   else
   {
       if (*this->ptMinimum > *m_vPoints[m_iPointsLength])
          this->ptMinimum = m_vPoints[m_iPointsLength];
   }
}
//------------------------------------------------
TConvexHull::TConvexHull()
{
   m_iPointsLength=0;
}
//------------------------------------------------
void TConvexHull::ComputeSlopes()
{
   for (int i=1; i<=m_iPointsLength; i++)
      this->m_vPoints[i]->ComputeSlope(this->ptMinimum);
}
//------------------------------------------------
double TConvexHull::CheckPoint(const TPoint* ptA, const TPoint* ptB, const TPoint* ptC)
{
    return (ptB->fX - ptA->fX) * (ptC->fY - ptA->fY) - (ptB->fY - ptA->fY) * (ptC->fX - ptA->fX);
}
//------------------------------------------------
bool SortFunction(TPoint* ptA,TPoint* ptB)
{
   return objHull->CheckPoint(objHull->ptMinimum, ptA, ptB) < 0;
}
//------------------------------------------------
void TConvexHull::Solve()
{
    this->ComputeSlopes();
    vector <TPoint*> vData;

    vData.push_back(this->ptMinimum);

    for (int i=1; i<=this->m_iPointsLength; i++)
       if (m_vPoints[i]!=this->ptMinimum)
          vData.push_back(this->m_vPoints[i]);
/*
    for (int i=0; i<vData.size(); i++)
       printf("%f %f %f\n",vData[i]->fX,vData[i]->fY,vData[i]->fSlope);
    printf("\n");*/

    sort(vData.begin()+1,vData.end(),SortFunction);
/*
    for (int i=0; i<vData.size(); i++)
       printf("%f %f %f\n",vData[i]->fX,vData[i]->fY,vData[i]->fSlope);*/


    int iStackPointer=1;
    int vStack[m_iPointsLength];
    vStack[0]=0;
    vStack[1]=1;


    for (int i=2; i<m_iPointsLength; i++)
    {
        while ((iStackPointer >= 2) && (this->CheckPoint(vData[vStack[iStackPointer - 1]], vData[vStack[iStackPointer]], vData[i]) > 0))
            iStackPointer-=1;

        iStackPointer++;
        vStack[iStackPointer] = i;
    }

    m_iHullLength=0;
    for (int i=iStackPointer; i>=0; i--)
    {
        m_vHull[m_iHullLength]=vData[vStack[i]];
        m_iHullLength++;
    }

}
//------------------------------------------------
//------------------------------------------------
//------------------------------------------------
void ReadData(TConvexHull * objHull)
{
   FILE * fIn = fopen("infasuratoare.in","r");

   int iN;
   double fX, fY;
   fscanf(fIn,"%d",&iN);

   for (int i=0; i<iN; i++)
   {
      fscanf(fIn,"%lf %lf",&fX,&fY);
      objHull->AddPoint(fX,fY);
   }

   fclose(fIn);
}
//------------------------------------------------
int main()
{
   objHull = new TConvexHull();

   ReadData(objHull);
   objHull->Solve();

   FILE * fOut = fopen("infasuratoare.out","w");
   fprintf(fOut,"%d\n",objHull->m_iHullLength);

   for (int i=0; i<objHull->m_iHullLength; i++)
      fprintf(fOut,"%lf %lf\n",objHull->m_vHull[i]->fX,objHull->m_vHull[i]->fY);

   fclose(fOut);
}