Cod sursa(job #241525)

Utilizator marcelcodreaCodrea Marcel marcelcodrea Data 10 ianuarie 2009 12:31:39
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.59 kb
//scanarea Graham (n log n)

#include<stdio.h>
#include<algorithm>

const double maxV = 1000000001;

struct Pct {
    double x;
    double y;
};
using namespace std;
Pct a[120002];
int poz[120002];
int pInit;
int stack[120002];
int top;
int n;
bool cmp(int i, int j)
{
    return ((a[j].y - a[pInit].y) * (a[i].x - a[pInit].x)) <  ((a[j].x - a[pInit].x) * (a[i].y - a[pInit].y));
}
int CrossProd(int i, int j, int k)
{
    return (((a[j].x - a[i].x) * (a[k].y - a[i].y) - (a[k].x - a[i].x) * (a[j].y - a[i].y)) > 0);
}
int main()
{
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);
    a[0].x = maxV;
    a[0].y = maxV;
    scanf("%d",&n);
    pInit = 0;
    for(int i = 1; i <= n; i++)
     {
         scanf("%lf %lf", &a[i].x, &a[i].y);
         if (a[i].y < a[pInit].y)
          {
              if (pInit)
              poz[++poz[0]] = pInit;
              pInit = i;
          }
          else
         if (a[i].y == a[pInit].y && a[i].x < a[pInit].x)
          {
              if (pInit)
              poz[++poz[0]] = pInit;
              pInit = i;
          }
          else
           poz[++poz[0]] = i;
     }
    sort(poz + 1, poz + poz[0] + 1, cmp);
    stack[1] = pInit;
    stack[2] = poz[1];
    top = 2;
    for(int i = 2; i < n; i++)
     {
         while (CrossProd(stack[top], stack[top-1], poz[i]) == 0) top--;
         top++;
         stack[top] = poz[i];
     }
     printf("%d\n",top);
     for(int i = 1; i <= top; i++)
      printf("%lf %lf\n", a[stack[i]].x, a[stack[i]].y);

    return 0;
}