Cod sursa(job #2073677)

Utilizator ApostolIlieDanielApostol Daniel ApostolIlieDaniel Data 23 noiembrie 2017 15:39:45
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.18 kb
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 120000;
const int INF = 2e9;

struct coord{double x; double y;};

coord v[MAXN + 1], st[MAXN + 1];
double S(coord a, coord b, coord c) {
  double A = 0;
  A = a.x * b.y - b.x * a.y + b.x * c.y - c.x * b.y + c.x * a.y - a.x * c.y;
  return A;
}

bool cmp(coord a, coord b) {
  if (S(v[1], a, b) >= 0)
    return true;
  return false;
}

int main() {
  double minx, miny;
  coord aux;
  int n, i, poz, vf;
  ifstream f("infasuratoare.in");
  ofstream g("infasuratoare.out");
  f >> n;
  minx = miny = INF;
  for (i = 1; i <= n; i++) {
    f >> v[i].x >> v[i].y;
    if (v[i].y < miny || (v[i].y == miny && v[i].x < minx)) {
      miny = v[i].y;
      minx = v[i].x;
      poz = i;
    }
  }
  aux = v[1];
  v[1] = v[poz];
  v[poz] = aux;
  sort(v + 2, v + n + 1, cmp);
  st[1] = v[1];
  st[2] = v[2];
  vf = 2;
  v[n + 1] = v[1];
  for (i = 3; i <= n + 1;i++) {
    while (vf >= 2 && S(st[vf -1 ], st[vf], v[i]) < 0)
      vf--;
      st[++vf]=v[i];
  }
  g << vf - 1 << '\n';
  for (i = 1; i < vf; i++) {
    g << setprecision(15) << st[i].x << ' ' << st[i].y << '\n';
  }
  return 0;
}