Cod sursa(job #1138181)

Utilizator hevelebalazshevele balazs hevelebalazs Data 9 martie 2014 18:04:31
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 kb
#include <stdio.h>
#include <stdlib.h>
#define fr(i,a,b) for(int i=a;i<b;++i)
#define rf(i,a,b) for(int i=b-1;i>=a;--i)
#define N 120000
int n,l;
double x[N],y[N];
int I[N],S[N],s;
int cp(int l,int a,int b){
    double x1=x[a]-x[l];
    double y1=y[a]-y[l];
    double x2=x[b]-x[l];
    double y2=y[b]-y[l];
    double p=x1*y1-x2*y1;
    return x1*y2-x2*y1<0?-1:1;
    }
int c(const void*a,const void*b){
    return cp(l,*(int*)a,*(int*)b);
    }
int main(){
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);
    scanf("%i",&n);
    fr(i,0,n){
        scanf("%lf%lf",x+i,y+i);
        if(x[i]<x[l])l=i;
        I[i]=i;
        }
    I[I[l]=0]=l;
    qsort(I+1,n-1,sizeof(*I),c);
    S[s++]=I[0];
    S[s++]=I[1];
    fr(i,2,n){
       while(cp(S[s-2],S[s-1],I[i])==1) --s;
       S[s++]=I[i];
       }
    printf("%i\n",s);
    rf(i,0,s)printf("%f %f\n",x[S[i]],y[S[i]]);
    return 0;
    }