Cod sursa(job #1675190)

Utilizator AnaRaduAna-Maria Radu AnaRadu Data 5 aprilie 2016 10:03:58
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
#include <stdio.h>
#include <algorithm>
#define lim 120005
#define maxim 1000000005
using namespace std;
int st[lim];
struct elem{float x,y;};
elem v[lim];
int tg(elem a,elem b,elem c){
    return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}
bool cmp(elem a,elem b){
    return tg(v[1],a,b)<0;
}
int main(){
    FILE *fin,*fout;
    fin=fopen("infasuratoare.in","r");
    fout=fopen("infasuratoare.out","w");
    int i,n,k=0;
    fscanf(fin,"%d",&n);
    v[k].x=maxim;
    v[k].y=maxim;
    for(i=1;i<=n;i++){
        fscanf(fin,"%f%f",&v[i].x,&v[i].y);
        if(v[i].x==v[k].x&&v[i].y<v[k].y)
            k=i;
        if(v[i].x<v[k].x)
            k=i;
    }
    v[n+1]=v[1];
    v[1]=v[k];
    v[k]=v[n+1];
    sort(v+2,v+n+1,cmp);
    st[1]=1;
    st[2]=2;
    k=2;
    for(i=3;i<=n;i++){
        while(k>=3&&tg(v[st[k-1]],v[st[k]],v[i])>0)
            k--;
        k++;
        st[k]=i;
    }
    fprintf(fout,"%d\n",k);
    for(i=k;i>=1;i--)
        fprintf(fout,"%0.6f %0.6f\n",v[st[i]].x,v[st[i]].y);
    fclose(fin);
    fclose(fout);
    return 0;
}