Cod sursa(job #1276527)

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

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

FILE *in;
FILE *out;

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)
{
  fprintf (out, "%.6lf %.6lf\n", p.x, p.y);
}

Punct* cautareBinara (int stanga, int dreapta, Punct punctCurent)
{
  int mijloc = (stanga + dreapta) >> 1;

  if (punctCurent.x == acoperireConvexa[mijloc][0].x)
    {
      if (punctCurent.y == acoperireConvexa[mijloc][0].y)
	return acoperireConvexa[mijloc];
      else if (punctCurent.y < acoperireConvexa[mijloc][0].y)
	return cautareBinara (stanga, mijloc - 1, punctCurent);
      else
	return cautareBinara (mijloc + 1, dreapta, punctCurent);
    }
  
  if (punctCurent.x < acoperireConvexa[mijloc][0].x)
    return cautareBinara (stanga, mijloc - 1, punctCurent);
  else
    return cautareBinara (mijloc + 1, dreapta, punctCurent);
}

int compare (const void *a, const void *b)
{
  const Punct *m1 = a;
  const Punct *m2 = b;

  if (m1[0].x == m2[0].x)
    {
      if (m1[0].y ==  m2[0].y)
	return 0;

      if (m1[0].y < m2[0].y)
	return -1;
      else
	return 1;
    }

  if (m1[0].x < m2[0].x)
    return -1;
  else
    return 1;
}

int main ()
{
  in = fopen ("infasuratoare.in",  "r");
  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;
	  }
      }

  fprintf (out, "%d\n", idx);
  
  Punct dummy[1][2]; 
  qsort (acoperireConvexa, idx, sizeof (dummy), &compare);
  
  printPunct (acoperireConvexa[0][0]);
  Punct punctCurent = acoperireConvexa[0][1];

  int diff = 1;
  while (diff < idx) {
    Punct *next = cautareBinara (0, idx, punctCurent);
    printPunct (next[0]);
    punctCurent = next[1];
    
    diff++;
  }
  
  fclose (in);
  fclose (out);

  return 0;
}