Cod sursa(job #1906869)

Utilizator geralt_of_riviajohn nathalis geralt_of_rivia Data 6 martie 2017 16:45:25
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
#include <stdio.h>
#include<algorithm>
using namespace std;
FILE *f,*g;
struct bla
{
    float x; float y;
} date[120010];
int n,vf,used[120010];
int st[120010];
void read ()
{
    fscanf(f,"%d",&n);
    for(int i=1;i<=n;i++)
        fscanf(f,"%f %f",&date[i].x,&date[i].y);
}
bool sortare (bla q,bla w)
{
    if(q.x==w.x) return q.y<w.y;
    return q.x<w.x;
}
int ec_dreptei (int q,int w,int e)
{
    bla a=date[q],b=date[w],c=date[e];
    return (c.x-a.x)*(a.y-b.y)-(c.y-a.y)*(a.x-b.x);
}
void infasuratoare ()
{
    sort(date+1,date+n+1,sortare);
    int urm=3,dir=1; vf=2;
    used[2]=1;
    st[1]=1; st[2]=2;
    while(used[1]==0)
    {
        while(used[urm]!=0)
        {
            if(urm==n) dir=-1;
            urm+=dir;
        }
        while(vf>1 && ec_dreptei(st[vf-1],st[vf],urm)<0) used[st[vf--]]=0;
        st[++vf]=urm;
        used[urm]=1;
    }
}
void write ()
{
    fprintf(g,"%d\n",vf-1);
    for(int i=1;i<vf;i++)
        fprintf(g,"%f %f\n",date[st[i]].x,date[st[i]].y);
}
int main()
{
    f=fopen("infasuratoare.in","r");
    g=fopen("infasuratoare.out","w");
    read();
    infasuratoare();
    write();
    fclose(f);
    fclose(g);
    return 0;
}