Cod sursa(job #1881264)

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

#define MAXN 120010

using namespace std;

struct point
{
  float 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, "%f %f", &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.x-a.x)*(a.y-b.y)-(a.x-b.x)*(c.y-a.y)<0) return true;
    return false;
}

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, "%.12f %.12f\n", puncte[st[i]].x, puncte[st[i]].y);
  }
  fclose(g);
}

int main()
{

  read();
  infasuratoare();
  write();
}