Cod sursa(job #821329)

Utilizator tzipleatudTudor Tiplea tzipleatud Data 22 noiembrie 2012 09:38:07
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.35 kb
#include <fstream>
#include <cmath>
#include <iomanip>
#include <algorithm>
#define NM 120010
#define INF 99999999999.0
#define EPS 1e-12
#define x first
#define y second

using namespace std;

ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");

double Equal (double A, double B)
{
  return fabs(A-B)<EPS;
}

typedef pair<double, double> PI;

PI G;

double Tang (PI P)
{
  if (Equal(P.x,G.x)) return INF;
  return 1.0*(P.y-G.y)/(P.x-G.x);
}

bool CMP (PI A, PI B)
{
  return Tang(A)<Tang(B);
}

int N;
int i,j;
int P;
PI V[NM];
PI S[NM];
int K;

int Sign (PI P1, PI P2, PI P3)
{
  double S=P1.x*P2.y+P2.x*P3.y+P3.x*P1.y-P1.x*P3.y-P2.x*P1.y-P3.x*P2.y;
  if (Equal(S,0.0)) return 0;
  return (S<0?-1:1);
}

int main ()
{
  f >> N;
  V[0].x=V[0].y=INF;
  for (i=1; i<=N; i++)
  {
    f >> V[i].x >> V[i].y;
    if (V[i].x<V[P].x || (Equal(V[i].x,V[P].x) && V[i].y<V[P].y))
      P=i;
  }

  swap(V[1],V[P]);
  G=V[1];
  sort(V+2,V+N+1,CMP);

  S[K=1]=V[1];

  for (i=2; i<=N; i++)
  {
    while (K>1 && Sign(S[K-1],S[K],V[i])<0) --K;
    S[++K]=V[i];
  }

  g << K << '\n';

  for (i=2; i<=K; i++)
    g << fixed << setprecision(12) << S[i].x << ' ' << S[i].y << '\n';

  g << fixed << setprecision(12) << S[1].x << ' ' << S[1].y << '\n';

  f.close();
  g.close();

  return 0;
}