Cod sursa(job #268828)

Utilizator yoyolichIoana Ardeleanu yoyolich Data 1 martie 2009 21:24:20
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.48 kb
#include<stdio.h>   
#include<stdlib.h>   
#define nmax 120010   
FILE *f=fopen("infasuratoare.in","r"), *g=fopen("infasuratoare.out","w");   
  
struct punct { double x,y;} a[nmax],pst;   
int n,i;   
inline int isleft(punct p1, punct p2, punct p3)   
{   
    return ((p2.x-p1.x)*(p3.y-p1.y)-(p3.x-p1.x)*(p2.y-p1.y));   
       
}   
  
inline int cmp(punct *p1, punct *p2)   
{   
    double left=isleft(pst,*p1,*p2);   
    if(left>0) return -1;   
    if(left==0) return 0;   
    if(left<0) return 1;   
}   
  
int main()   
{   
    fscanf(f,"%d",&n);   
    for(i=1;i<=n;i++)   
        fscanf(f,"%lf %lf",&a[i].x, &a[i].y);   
       
    pst=a[1];   
    int poz=1;   
       
    for(i=2;i<=n;i++)   
        if(a[i].y<pst.y) pst=a[i],poz=i;   
        else  
            if(a[i].y==pst.y)   
                if(a[i].x<pst.x) pst=a[i],poz=i;   
       
    punct aux;   
    aux=a[1];   
    a[1]=a[poz];    
    a[poz]=aux;   
       
    qsort(a+2,n-1,sizeof(punct), (int (*)(const void *, const void *))cmp);   
       
    punct stiva[nmax];   
    int k=0;   
    stiva[++k]=a[1];   
    stiva[++k]=a[2];   
    stiva[++k]=a[3];   
    for(i=4;i<=n;i++)   
    {   
        while(isleft(stiva[k-1],stiva[k],a[i])<0) k--;   
        stiva[++k]=a[i];   
    }     
    fprintf(g,"%d\n",k);   
    for(i=1;i<=k;i++) fprintf(g,"%.6lf %.6lf\n",stiva[i].x,stiva[i].y);   
       
    fclose(f);   
    fclose(g);   
    return 0;   
}