Cod sursa(job #348952)

Utilizator doru.nituNitu Doru Constantin doru.nitu Data 17 septembrie 2009 17:44:16
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.59 kb
#include<stdio.h>
#include<algorithm>
using namespace std;

int i,n,d,sor[12010],stiva[12010];

struct point
{ long double x,y;
}p[120010],q;

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

bool comp( int i, int j)
{ if( isleft( p[0],p[i],p[j])>0) return 1;
  return 0;
}

int main()
{ 
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);
    
    scanf("%d",&n);
    scanf("%LE %LE",&p[0].x,&p[0].y);
    q=p[0];
    for(i=1;i<n;i++) { scanf("%LE %LE",&p[i].x,&p[i].y);
                       if(p[i].y<p[0].y||(p[i].y==p[0].y&&p[i].x>p[0].x)) { q=p[i];
                                                                             p[i]=p[0];
                                                                             p[0]=q;
                                                                           }
                      sor[i]=i;                                                     
                     }
    p[n]=p[0];
    p[n+1]=p[1];                 
    sort(sor+1,sor+n,comp);
      
    
    for(i=1;i<n;i++) { while(d>0&&isleft(p[stiva[d-1]],p[stiva[d]],p[sor[i]])<=0) d--;
                       stiva[++d]=sor[i];
                     }   
                     
    printf("%d\n",d+1);
    for(i=0;i<=d;i++) printf("%LE %LE\n",p[stiva[i]].x,p[stiva[i]].y);
    
    fclose(stdin);
    fclose(stdout);
    
    return 0;
}