Cod sursa(job #2374844)

Utilizator stefan_creastaStefan Creasta stefan_creasta Data 7 martie 2019 20:47:49
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.44 kb
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
const int NMAX = 120005;
const int INF = 1000000000;
const double eps = 1.e-12;
struct Punct {
  double x,y ;
};
int st[NMAX];
Punct v[NMAX];
Punct ll;
double d(Punct p1, Punct p2, Punct p3) {
  return (p2.x - p1.x) * (p3.y - p2.y) - (p2.y - p1.y) * (p3.x - p2.x);
}
int u(Punct p1, Punct p2, Punct p3) {
  double det = d(p1, p2, p3);
  if(fabs(det) < eps) {
    return 0;
  }
  else {
    if(det >= eps) {
      return 1;
    }
    else {
      return -1;
    }
  }
}
bool cmp(Punct first, Punct second) {
  int cp = u(ll, first, second);
  if(cp == 1) {
    return 1;
  }
  else {
    return 0;
  }
}

int main() {
  int n;
  freopen("infasuratoare.in", "r", stdin);
  freopen("infasuratoare.out", "w", stdout);
  scanf("%d", &n);
  ll.x = ll.y = INF;
  for(int i = 0; i < n; i++) {
    scanf("%lf%lf", &v[i].x, &v[i].y);
    bool ok = 0;
    if(ll.y - v[i].y >= eps) {
      ok = 1;
    }
    else if(fabs(ll.y - v[i].y) < eps){
      if(ll.x - v[i].x >= eps) {
        ok = 1;
      }
    }
    if(ok == 1) {
      swap(ll, v[i]);
    }
  }
  v[0] = v[n] = ll;
  sort(v + 1, v + n, cmp);
  st[0] = 0;
  st[1] = 1;
  int top = 1;
  for(int i = 2; i <= n; i++) {
    while(top >= 1 && u(v[st[top - 1]], v[st[top]], v[i]) <= 0) {
      top--;
    }
    st[++top] = i;
  }
  printf("%d\n", top);
  for(int i = 0; i < top; i++) {
    printf("%lf %lf\n", v[st[i]].x, v[st[i]].y);
  }
  return 0;
}