Cod sursa(job #266996)

Utilizator FlorianFlorian Marcu Florian Data 26 februarie 2009 16:45:29
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.56 kb
#include<stdio.h>
#define ll double
#include<stdlib.h>
#define Nmax 120000
#define EPS 1e-12
FILE*f=freopen("infasuratoare.in","r",stdin);
FILE*g=freopen("infasuratoare.out","w",stdout);
struct Punct
 {
  double x,y;
 };
Punct P[Nmax], v[Nmax], a[Nmax];
int n;
int comp(double x, double y)
 {
  if(x+EPS < y) return -1;
  if(y+EPS < x) return +1;
  return 0;
 }
int cmp(const void *a, const void *b)
 {
  int i=*(int*)a, j=*(int*)b;
  if(v[i].x == v[j].x) return v[i].y - v[j].y;
  return v[i].x - v[j].x;
 }
void sortare()
 {
  int ord[Nmax];
  int i;
  for(i=0;i<=n;++i) ord[i] = i;
  v[0].x = v[0].y = -1000000003;
  qsort(ord,n+1,sizeof(long int),cmp);
  for(i=1;i<=n;++i) a[i] = v[ord[i]];
 }
void read()
 {
  int i;
  scanf("%d",&n);
  for(i=1;i<=n;++i) scanf("%lf %lf",&v[i].x, &v[i].y);
 }
inline int semn(Punct P1, Punct P2, Punct P3)
 {
  ll A = P3.x * (P1.y-P2.y);
  ll B = P3.y * (P2.x-P1.x);
  ll C = P1.x * P2.y - P2.x * P1.y;
  return comp(A+B+C,0);
 }
int uz[Nmax];
int H;
void convexHull()
 {
  int pas=+1, i=3, k=2, st[Nmax];
  st[1] = 1; st[2] = 2; uz[2]=1;
  while(!uz[1])
   {
    while(uz[i])
     {
      if(i==n) pas = -1;
      i+=pas;
     }
    while(k>=2 && semn(a[st[k-1]], a[st[k]],a[i]) == -1) uz[st[k--]] = 0;

    st[++k] = i; uz[i] = 1;
   }
  H = k - 1;
  for(i=1;i<=H;++i) P[i] = a[st[i]];
 }
void afisare()
 {
  int i;
  printf("%d\n",H);
  for(i=1;i<=H;++i) printf("%.6lf %.6lf\n",P[i].x,P[i].y);
 }
int main()
 {
  read();
  sortare();
  convexHull();
  afisare();
  return 0;
 }