Cod sursa(job #759464)

Utilizator test13test13 test13 Data 18 iunie 2012 11:48:39
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.37 kb
#include <cstdio>
#include <algorithm>
using namespace std;
#define MAX 120001

struct point{   double x,y;    }g[MAX],l[MAX],r[MAX]; //number of points

int n,nl,nr;

bool cmp(point a,point b){ return a.x<b.x; }

long double delta(point a,point b,point c){
    return a.x*b.y+b.x*c.y+c.x*a.y-
    c.x*b.y-a.x*c.y-b.x*a.y;
}

void split(){
    point p,u; // first and last point
    p = g[0]; // saving first point
    u = g[n-1]; // saving last point
    l[0]=r[0]=p;
    for(int i=1;i<n-1;i++)
    {
        //printf("%lf %lf %lf %lf %lf %lf %lf\n",p.x,p.y,g[i].x,g[i].y,u.x,u.y,delta(p,u,g[i]));
        if(delta(p,u,g[i])>0)l[++nl]=g[i]; // this point go to the up subset
        else r[++nr]=g[i]; // this point go to the down subset
    }
    l[++nl]=r[++nr]=u; // putting last point
    ++nl;
    ++nr;
  //  printf("%lf %lf %lf %lf\n",p.x,p.y,u.x,u.y);
}

void convex_up(){
    int n; // number of points in current convex envelope
    n = 2; // first 2 points goes in subset
    for(int i=2;i<nl;i++) //for rest of points
    {
      //  printf("%lf %lf\n",g[i].x,g[i].y);
        while(n>1 && delta(l[n-2],l[i],l[n-1])-0.000001<0)n--;
        l[n++]=l[i];
    }
    nl=n;
}

void convex_down(){
    int n; // number of points in current convex envelope
    n = 2; // first 2 points goes in subset
    for(int i=2;i<nr;i++) // for rest of points
    {
        while(n>1 && delta(r[n-2],r[i],r[n-1])+0.000001>0)n--;
        r[n++]=r[i];
    }
    nr=n;
}

int main(){
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);
        scanf("%d",&n);
        // reading points
        for(int i=0;i<n;i++)scanf("%lf %lf",&g[i].x,&g[i].y);
        // sorting points
        sort(g,g+n,cmp);
        // split into 2 subsets { up, down }
        split();
        // processing up subset
        convex_up();
        // processing down subset
        convex_down();

    printf("%d\n",nl+nr-2);
    for(int i=0;i<nr;i++)printf("%lf %lf\n",r[i].x,r[i].y);
    for(int i=nl-2;i>0;i--)printf("%lf %lf\n",l[i].x,l[i].y);

  /*  point a,b,c;
    a.x=0.0; a.y=0.0;
    b.x=2.0; b.y=0.0;
    c.x=1.0; b.y=1.0;
    printf("%lf\n",delta(a,c,b)); */
  //  for(int i=0;i<nl;i++)printf("%lf %lf\n",l[i].x,l[i].y);printf("-----------------\n");
   // for(int i=0;i<nr;i++)printf("%lf %lf\n",r[i].x,r[i].y);
    return 0;
}