Pagini recente » Cod sursa (job #1176904) | Cod sursa (job #1137490) | Cod sursa (job #705278) | Cod sursa (job #2825396) | Cod sursa (job #1046333)
#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(ptA, ptB, objHull->ptMinimum) < 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);
}