Cod sursa(job #1824936)

Utilizator roxana.aeleneiAelenei Roxana roxana.aelenei Data 8 decembrie 2016 16:30:47
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.36 kb
#include <cstdio>
#include <cmath>
#include <algorithm>
#define eps 1.e-12
using namespace std;
int const NMAX=120000;
struct point
{
    double x,y;
}LL,p[NMAX+5];
int h[NMAX+5];

int ccw(point p1, point p2, point p3)
{
    double cp;
    cp=(p2.x-p1.x)*(p3.y-p2.y)-(p2.y-p1.y)*(p3.x-p2.x);
    if(fabs(cp)< eps) return 0;
    if(cp >= eps) return 1;
    return -1;
}

bool cmp(point a, point b)
{
    int c=ccw(LL,a,b);
    if(c == 1) return 1;
    if(c == -1) return 0;
}

int main()
{
    freopen("infasuratoare.in", "r",stdin);
    freopen("infasuratoare.out", "w",stdout);
    int n;
    scanf("%d", &n);
    for(int i=0; i<n; i++)
        scanf("%lf%lf",&p[i].x, &p[i].y);
    LL=p[0];
    for(int i=1; i<n; i++)
        if(LL.y > p[i].y)
         LL=p[i];
        else if(LL.y == p[i].y && LL.x < p[i].x)
         LL=p[i];
    sort(p, p+n,cmp);

    //printf("%lf %lf\n", LL.x, LL.y);
    //for(int i=0; i<n ;i++)
      //  printf("%lf %lf\n", p[i].x, p[i].y);
      p[n]=LL;
      h[0]=0;
      h[1]=1;
      int top=1,i=2;
      while(i<=n)
      {
          if(ccw(p[h[top-1]],p[h[top]], p[i]) > 0){
        top++;
        h[top]=i;
        i++;
          }
          else top--;
      }
      printf("%d\n", top);
      for(int i=0; i<top; i++)
        printf("%.6lf %.6lf\n",p[h[i]].x,p[h[i]].y);
    return 0;
}