Cod sursa(job #1894837)

Utilizator oanaroscaOana Rosca oanarosca Data 27 februarie 2017 16:39:13
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.32 kb
#include <fstream>
#include <algorithm>
#include <iomanip>

using namespace std;

struct punct {
  double x, y;
};

bool cmp (punct a, punct b) {
  if (a.x < b.x or (a.x == b.x and a.y < b.y))
    return true;
  return false;
}

bool semn (punct a, punct b, punct c) {
  if ((a.x*b.y + b.x*c.y + a.y*c.x - b.y*c.x - a.x*c.y - b.x*a.y) >= 0)
    return true;
  return false;
}

punct a[101], st[1001];
int n, sf = 2;

int main () {
  ifstream fi("infasuratoare.in");
  ofstream fo("infasuratoare.out");
  fi >> n;
  for (int i = 1; i <= n; i++)
    fi >> a[i].x >> a[i].y;
  sort (a+1, a+n+1, cmp);
  st[1] = a[1], st[2] = a[2];
  for (int i = 3; i <= n; i++) {
    while (sf > 1 and !semn(st[sf-1], st[sf], a[i]))
      sf--;
    st[++sf] = a[i];
  }
  for (int i = n-1; i >= 1; i--) {
    while (!semn(st[sf-1], st[sf], a[i]))
      sf--;
    st[++sf] = a[i];
  }
  fo << sf-1 << '\n';
  int xmin = 2e9, ymin = 2e9, inc = 1;
  for (int i = 1; i <= sf-1; i++)
    if (st[i].y < ymin or (st[i].y == ymin and st[i].x < xmin))
      ymin = st[i].y, xmin = st[i].x, inc = i;
  fo << fixed << setprecision(6);
  for (int i = inc; i <= sf-1; i++)
    fo << st[i].x << ' ' << st[i].y << '\n';
  if (inc != 1)
    for (int i = 1; i <= inc-1; i++)
      fo << st[i].x << ' ' << st[i].y << '\n';
  return 0;
}