Cod sursa(job #1881291)

Utilizator stefan_bogdanstefan bogdan stefan_bogdan Data 16 februarie 2017 12:42:42
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.52 kb
#include <iostream>
#include <stdio.h>
#include <algorithm>

#define MAXN 120010

using namespace std;

struct point
{
  double x, y;
};

int st[MAXN];
int used[MAXN];
int urmator, dir;
int vf;
int n;
point puncte[MAXN];

bool how(point a, point b)
{
  if (a.x == b.x)
  {
    return a.y < b.y;
  }
  return a.x < b.x;
}

void read()
{
  FILE * f = fopen("infasuratoare.in", "r");

  fscanf(f, "%d", &n);

  for (int i = 1; i <= n; i++)
  {
    fscanf(f, "%lf %lf", &puncte[i].x, &puncte[i].y);
  }
  /* sortare puncte dupa x, apoi y*/
  sort(puncte + 1, puncte + n + 1, how);

  fclose(f);
}

int ecdreptei(point a, point b, point c)
{
  if ((c.y - a.y) * (b.x - a.x) - (c.x - a.x) * (b.y - a.y) < 0) return 1;
  return 0;
}

void infasuratoare()
{
  st[++vf] = 1;
  st[++vf] = 2;
  used[2] = 1;
  dir = 1;
  urmator = 3;
  /* cat timp nu am ajuns de unde am plecat*/
  while (used[1] == 0)
  {
    while (used[urmator] != 0)
    {
      if (urmator == n)
      {
        dir = -1;
      }
      urmator += dir;
    }
    while (vf >= 2 && ecdreptei(puncte[st[vf - 1]], puncte[st[vf]], puncte[urmator]))
    {
      used[st[vf--]] = 0;
    }
    st[++vf] = urmator;
    used[urmator] = 1;
  }
}

void write()
{
  FILE * g = fopen("infasuratoare.out", "w");
  fprintf(g, "%d\n", vf - 1);
  for (int i = 1; i < vf; i++)
  {
    fprintf(g, "%.6lf %.6lf\n", puncte[st[i]].x, puncte[st[i]].y);
  }
  fclose(g);
}

int main()
{
  read();
  infasuratoare();
  write();
}