Cod sursa(job #1826478)

Utilizator roxana.aeleneiAelenei Roxana roxana.aelenei Data 10 decembrie 2016 14:59:07
Problema Infasuratoare convexa Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.29 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 >= eps)
         LL=p[i];
        else if((fabs(p[i].y-LL.y) < eps) && (LL.x - p[i].x >= eps))
         LL=p[i];
    sort(p+1, p+n, cmp);

      p[0]=LL;
      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;
}