Cod sursa(job #1276480)

Utilizator bghimisFMI Ghimis Bogdan bghimis Data 26 noiembrie 2014 14:45:08
Problema Infasuratoare convexa Scor 0
Compilator c Status done
Runda Arhiva educationala Marime 1.55 kb
#include <stdio.h>
#include <assert.h>

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

Punct setPuncte[120000];
Punct acoperireConvexa[120000][2];

int testOrientare (Punct p, Punct q, Punct r)
{
  int x1 = p.x; int x2 = q.x; int x3 = r.x;
  int y1 = p.y; int y2 = q.y; int y3 = r.y;

  return ((x2 - x1) * (y3 - y1) - (x3 - x1) * (y2 - y1));
}

void printPunct (Punct p)
{
  printf ("%.6lf %.6lf\n", p.x, p.y);
}

int main ()
{
  FILE *in  = fopen ("infasuratoare.in",  "r");
  FILE *out = fopen ("infasuratoare.out", "w");

  int n;
  assert (fscanf (in, "%d", &n) == 1);

  int i, j, k;
  for (i = 0; i < n; ++i)
    assert (fscanf (in, "%lf%lf", &setPuncte[i].x, &setPuncte[i].y) == 2);
  
  int valid; int idx = 0;
  for (i = 0; i < n; ++i)
    for (j = 0; j < n; ++j)
      {
	if (i == j) continue;
	
	valid = 1;
	for (k = 0; k < n; ++k)
	  if (i != k && j != k &&
	      testOrientare (setPuncte[i], setPuncte[j], setPuncte[k]) < 0)
	    {
	      valid = 0;
	      break;
	    }

	if (valid == 1)
	  {
	    acoperireConvexa [idx][0] = setPuncte[i];
	    acoperireConvexa [idx][1] = setPuncte[j];
	    ++idx;
	  }
      }
  
  printPunct (acoperireConvexa[0][0]);
  Punct punctCurent = acoperireConvexa[0][1];

  int diff = 1;

  while (diff < idx) {
    for (i = 0; i < idx; ++i)
      {
	if (acoperireConvexa[i][0].x == punctCurent.x &&
	    acoperireConvexa[i][0].y == punctCurent.y)
	  {
	    printPunct (acoperireConvexa [i][0]);
	    punctCurent = acoperireConvexa [i][1];
	    diff++;
	    
	    break;
	  }
      }
  }
  
  fclose (in);
  fclose (out);

  return 0;
}