Cod sursa(job #269405)

Utilizator alecmanAchim Ioan Alexandru alecman Data 2 martie 2009 21:06:57
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.85 kb
#include<cstdio>
#include<algorithm>

using namespace std;

#define INPUT "infasuratoare.in"
#define OUTPUT "infasuratoare.out"
#define NMAX 120001
#define INFI 2000000000

FILE *fin = fopen(INPUT, "r"), *fout = fopen(OUTPUT, "w");

struct AngleStruct
{
  long double val;
  long pos;
};

long N, Pmin;
long Stack[ NMAX ];
long double X[ NMAX ], Y[ NMAX ];
AngleStruct Angle[ NMAX ];

void readData()
{
  fscanf(fin, "%ld", &N);

  Pmin = 0;

  for(long i = 0; i < N; ++i)
  {
    fscanf(fin, "%Lf %Lf", &X[ i ], &Y[ i ]);
    
    if((X[ Pmin ] > X[ i ]) || (X[ Pmin ] == X[ i ] && Y[ Pmin ] > Y[ i ]))
      Pmin = i;
  }
}

void detAngles()
{
  for(long i = 0; i < N; ++i)
  {
    if(X[ i ] != X[ Pmin ])
      Angle[ i ].val = (Y[ i ] - Y[ Pmin ]) / (X[ i ] - X[ Pmin ]);
    else
      Angle[ i ].val = INFI; 
    
    Angle[ i ].pos = i;
  }
}

inline int cmp(AngleStruct _X, AngleStruct _Y)
{
  return ((long double)_X.val < (long double)_Y.val)||((long double)_X.val == (long double)_Y.val && (X[_X.pos] < X[_Y.pos] || Y[_X.pos] > Y[_Y.pos]));
}

inline long double sign(long Poz)
{
  long V1 = Stack[ Poz - 2 ];
  long V2 = Stack[ Poz - 1 ];
  long V3 = Stack[ Poz ];

  return (X[V1]*Y[V2]+X[V2]*Y[V3]+X[V3]*Y[V1]-Y[V1]*X[V2]-Y[V2]*X[V3]-Y[V3]*X[V1]);
}

void solve()
{
  Stack[ 0 ] = Pmin;
  long posit = 0;

  for(long i = 0; i < N; ++i)
  {
    Stack[ ++posit ] = Angle[ i ].pos;

    /*for(long j = 0; j <= posit; ++j)
      fprintf(stderr, "%ld ", Stack[ j ]);
    fprintf(stderr, "\n");*/

    while(posit >= 2 && sign(posit) < 0)
    {
      Stack[ posit - 1 ] = Stack[ posit ];
      --posit;
    }
  }

  fprintf(fout, "%ld\n", posit);

  for(long i = 1; i <= posit; ++i)
    fprintf(fout, "%.6Lf %.6Lf\n", X[ Stack[ i ] ], Y[ Stack[ i ] ]);
}

int main()
{
  readData();

  detAngles();

  sort(Angle, Angle + N, cmp);

  solve();

  fclose(fin);
  fclose(fout);

  return 0;
}