Cod sursa(job #2211581)

Utilizator NaritaandreiCNAINarita Andrei NaritaandreiCNAI Data 10 iunie 2018 22:25:23
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.2 kb
#include <stdio.h>
#include <algorithm>
using namespace std;
FILE *f,*g;
struct point
{
    double x,y;
}v[120002];
bool been[120002];
int st[120002];
int n,h;
bool cmp (point a, point b)
{
    if(a.x!=b.x)
        return a.x<b.x;
    return a.y<b.y;
}

void read()
{
    fscanf(f,"%d",&n);
    for(int i=1; i<=n; i++)
        fscanf(f,"%lf %lf",&v[i].x,&v[i].y);
    sort(v+1,v+n+1,cmp);
}
double determinant(point a, point b, point c)
{
    return ((a.x*b.y+b.x*c.y+c.x*a.y)-(b.y*c.x+c.y*a.x+a.y*b.x));
}
void infasuratoare()
{   int k,i,q;
    st[1]=1,st[2]=2;
    been[2]=1;
    k=2;
    i=3;
    q=1;
    while(!been[1])
    {
        while(been[i])
        {
            if(i==n)
                q=-1;
            i+=q;
        }
        while(k>=2 && determinant(v[st[k-1]],v[st[k]],v[i])<0)
            been[st[k--]]=0;
        st[++k]=i;
        been[i]=1;
    }
    h=k-1;
}
int main()
{   int p;
    f=fopen("infasuratoare.in","r");
    g=fopen("infasuratoare.out","w");
    read();
    infasuratoare();
    fprintf(g,"%d\n",h);
    for(int i=1; i<=h; i++)
        fprintf(g,"%6f %6f\n",v[st[i]].x,v[st[i]].y);
    fclose(f);
    fclose(g);
    return 0;
}