Cod sursa(job #770389)

Utilizator XladhenianGrigorita Vlad-Stefan Xladhenian Data 22 iulie 2012 20:56:04
Problema Infasuratoare convexa Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 2.67 kb

#include <fstream>
#include <iomanip>
#include <stdlib.h>
using namespace std;

double mydabs(double x)
{
 if (x < 0)
   {
    return -x;
   }
 return x;
}

struct TPoint
{
 double X,Y;
};


TPoint Points[125000];
int Index[125000];
int LowestYIndex;
int Stack[125000];
int StackPos;

double Dot(double X1,double Y1,double X2,double Y2)
{
 return X1 * X2 + Y1 * Y2;
}

double Cross(double X1,double Y1,double X2,double Y2)
{
 return X1 * Y2 - X2 * Y1;
}

int SortFunc(const void *P1,const void *P2)
{
 int i1 = *((int *)(P1));
 int i2 = *((int *)(P2));
 double x1 = Points[i1].X - Points[LowestYIndex].X;
 double y1 = Points[i1].Y - Points[LowestYIndex].Y;
 double x2 = Points[i2].X - Points[LowestYIndex].X;
 double y2 = Points[i2].Y - Points[LowestYIndex].Y;
// double res = mydabs(Cross(x1,y1,x2,y2)) / Dot(x1,y1,x2,y2);
 double res = Cross(x1,y1,x2,y2) / Dot(x1,y1,x2,y2);
 if (res < 0)
   {
    return 1;
   }
  else
   {
    return -1;
   }
}

void Push(int i)
{
 Stack[StackPos] = i;
 StackPos += 1;
}

int Pop(void)
{
 int res = Stack[StackPos];
 StackPos -= 1;
 return res;
}

int main(void)
{
 fstream fin("infasuratoare.in",ios::in);
 fstream fout("infasuratoare.out",ios::out);
 long N;
 fin >> N;
 LowestYIndex = 0;
 for (int i = 0;i < N;i += 1)
 {
  fin >> Points[i].X >> Points[i].Y;
  Index[i] = i;
  if (Points[i].X < Points[LowestYIndex].X)
    {
     LowestYIndex = i;
    }
 }

 Index[0] = LowestYIndex;
 Index[LowestYIndex] = 0;

 qsort(Index + 1,N - 1,sizeof(int),SortFunc);

 Push(LowestYIndex);
 Push(Index[1]);
 Push(Index[2]);
 Index[N] = LowestYIndex;

 for (int i = 3;i <= N;i += 1)
  {
   double x1 = Points[Index[i]].X - Points[Stack[StackPos - 2]].X;
   double y1 = Points[Index[i]].Y - Points[Stack[StackPos - 2]].Y;
   double x2 = Points[Stack[StackPos - 1]].X - Points[Stack[StackPos - 2]].X;
   double y2 = Points[Stack[StackPos - 1]].Y - Points[Stack[StackPos - 2]].Y;
   while (Cross(x1,y1,x2,y2) >= 0)
    {
     Pop();
     x1 = Points[Index[i]].X - Points[Stack[StackPos - 2]].X;
     y1 = Points[Index[i]].Y - Points[Stack[StackPos - 2]].Y;
     x2 = Points[Stack[StackPos - 1]].X - Points[Stack[StackPos - 2]].X;
     y2 = Points[Stack[StackPos - 1]].Y - Points[Stack[StackPos - 2]].Y;
    }
   Push(Index[i]);
  }

 StackPos -= 1;

 fout << StackPos << "\n";


 char OutString[200];
 for (int i = 0;i < StackPos;i += 1)
  {
   sprintf(OutString,"%.6lf %.6lf\n",Points[Stack[i]].X,Points[Stack[i]].Y);
//   fout << setprecision(15) << Points[Stack[i]].X << " " << Points[Stack[i]].Y << "\n";
   fout << OutString;
  }

 fin.close();
 fout.close();
 return 0;
}