Cod sursa(job #1276605)

Utilizator bghimisFMI Ghimis Bogdan bghimis Data 26 noiembrie 2014 17:02:15
Problema Infasuratoare convexa Scor 0
Compilator c Status done
Runda Arhiva educationala Marime 1.82 kb
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef struct
{
  double x;
  double y;
} Point;

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 (p.x == q.x)
    {
      if (p.y == q.y)
	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, "%.6lf %.6lf\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 >= 1 && testOrientare (Lupper[uk - 2], Lupper[uk - 1], Lupper[uk]) > 0)
	{
	  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 >= 1 && testOrientare (Llower [lk - 2], Llower[lk - 1], Llower [lk]) > 0)
	{
	  Llower [lk - 1] = Llower [lk];
	  lk--;
	}

      lk++;
    }

  fprintf (out, "%d\n", lk + uk - 2);
  for (i = 0; i < uk; ++i)
    printPoint (Lupper[i]);

  for (i = 1; i < lk - 1; ++i)
    printPoint (Llower[i]);
  
  return 0;
}