Cod sursa(job #770071)

Utilizator XladhenianGrigorita Vlad-Stefan Xladhenian Data 21 iulie 2012 21:27:40
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.08 kb

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

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 = 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].Y < Points[LowestYIndex].Y)
    {
     LowestYIndex = i;
    }
 }

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

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

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

 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;
   if (Cross(x1,y1,x2,y2) >= 0)
     {
      Pop();
     }
   Push(Index[i]);
  }      
 
 for (int i = 0;i < StackPos;i += 1)
  {
   fout << setprecision(10) << Points[Stack[i]].X << " " << Points[Stack[i]].Y << "\n";
  }

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