Cod sursa(job #1277155)

Utilizator bghimisFMI Ghimis Bogdan bghimis Data 27 noiembrie 2014 11:19:37
Problema Infasuratoare convexa Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 2.11 kb
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <math.h>
 
typedef struct
{
  double x;
  double y;
} Point;

const double EPS = 0.000000000001;

int testOrientare (Point p, Point q, Point r)
{
  double x1 = p.x; double x2 = q.x; double x3 = r.x;
  double y1 = p.y; double y2 = q.y; double y3 = r.y;
 
  return ((x2 - x1) * (y3 - y1) - (x3 - x1) * (y2 - y1));
}
 
Point setPoints[120000];
Point Lupper [120000];
Point Llower [120000];
 
FILE *in;
FILE *out;
 
int compare (const void *a, const void *b)
{
  Point p = *(Point *) a;
  Point q = *(Point *) b;
 
  if (fabs(p.x - q.x) < EPS)
    {
      if (fabs(p.y - q.y) < EPS)
    return 0;
      else if (p.y < q.y)
    return -1;
      else
    return 1;
    }
 
  if (p.x < q.x)
    return -1;
  else
    return 1;
}
 
void printPoint (Point p)
{
  fprintf (out, "%.12lf %.12lf\n", p.x, p.y);
}
 
int main()
{
  in  = fopen ("infasuratoare.in", "r");
  out = fopen ("infasuratoare.out", "w");
 
  int n;
  assert (fscanf (in, "%d", &n) == 1);
 
  int i;
  for (i = 0; i < n; ++i)
    assert (fscanf (in, "%lf%lf", &setPoints[i].x, &setPoints[i].y) == 2);
 
  qsort (setPoints, n, sizeof (Point), &compare);
   
  Lupper [0] = setPoints[0];
  Lupper [1] = setPoints[1];
  int uk = 2;
  for (i = 2; i < n; ++i)
    {
      Lupper [uk] = setPoints[i];
 
      while (uk >= 2 && (testOrientare (Lupper[uk - 2], Lupper[uk - 1], Lupper[uk]) > 0 ||
			 fabs (testOrientare (Lupper[uk - 2], Lupper[uk - 1], Lupper[uk])) < EPS))
	{
	  Lupper [uk - 1] = Lupper [uk];
	  uk--;
	}
       
      uk++;
    }
 
  Llower [0] = setPoints[n - 1];
  Llower [1] = setPoints[n - 2];
  int lk = 2;
  for (i = n - 3; i >= 0; --i)
    {
      Llower [lk] = setPoints[i];
       
      while (lk >= 2 && (testOrientare (Llower [lk - 2], Llower[lk - 1], Llower [lk]) > 0 ||
			 fabs (testOrientare (Llower [lk - 2], Llower[lk - 1], Llower [lk])) < EPS))
	{
	  Llower [lk - 1] = Llower [lk];
	  lk--;
	}
       
      lk++;
    }
 
  fprintf (out, "%d\n", lk + uk - 2);
  for (i = uk - 1; i >= 0; --i)
    printPoint (Lupper[i]);
 
  for (i = lk - 2; i >= 1; --i)
    printPoint (Llower[i]);
   
  return 0;
}