Cod sursa(job #1954529)

Utilizator MiricaMateiMirica Matei MiricaMatei Data 5 aprilie 2017 14:37:40
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.28 kb
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
const int NMAX = 120000;
struct Punct{
  double x, y;
};
Punct v[NMAX + 5];
double cross_product(Punct P1, Punct P2, Punct P3){
  return (P2.x - P1.x) * (P3.y - P2.y) -
     (P2.y - P1.y) * (P3.x - P2.x);
}
int ccw(Punct P1, Punct P2, Punct P3){
  double cp = cross_product(P1, P2, P3);
  if (cp < 0)
    return -1;
  if (cp > 0)
    return 1;
  return 0;
}
bool cmp(Punct a, Punct b){
  return ccw(v[0], a, b) > ccw(v[0], b, a);
}
int st[NMAX + 5];
int main(){
  freopen("infasuratoare.in", "r", stdin);
  freopen("infasuratoare.out", "w", stdout);
  int n, ind = 0;
  scanf("%d", &n);
  for (int i = 0; i < n; ++i){
    double x, y;
    scanf("%lf%lf", &x, &y);
    v[i] = {x, y};
    if (v[i].y < v[ind].y || (v[i].y == v[ind].y && v[i].x < v[ind].x))
      ind = i;
  }
  swap(v[0], v[ind]);
  sort(v + 1, v + n, cmp);
  st[0] = 0;
  st[1] = 1;
  int top = 1;
  v[n] = v[0];
  for (int i = 2; i <= n; ++i){
    while (top > 1 && ccw(v[st[top]], v[st[top - 1]], v[i]) != ccw(v[st[top]], v[st[top - 1]], v[st[top - 2]]))
      top--;
    st[++top] = i;
  }
  printf("%d\n", top);
  for (int i = 0; i < top; ++i){
    printf("%f %f\n", v[st[i]].x, v[st[i]].y);
  }
  return 0;
}