Cod sursa(job #1628905)

Utilizator QQQ1911Vodita Stefan QQQ1911 Data 4 martie 2016 11:26:46
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.25 kb
#include <stdio.h>
#include <algorithm>
#include <math.h>
using namespace std;

int n,q,nr=2,s[120001];
struct punct
{
    double x,y,tg;
} a[120001];

void cit()
{
    scanf("%d ",&n);
    int i;
    for(i=1; i<=n; ++i)
        scanf("%f %f ",&a[i].x,&a[i].y);
}

void afis()
{
    printf("%d\n",nr);
    int i;
    for(i=1; i<=nr; ++i)
        printf("%f %f\n",a[s[i]].x,a[s[i]].y);
}

void aleg()
{
    int i;
    double miny=1000000000,minx=1000000000;
    for(i=1; i<=n; ++i)
    {
        if(miny>a[i].y)
        {
            miny=a[i].y;
            minx=a[i].x;
            q=i;
        }
        else if(miny==a[i].y&&minx>a[i].x)
        {
            minx=a[i].x;
            q=i;
        }
    }
    //printf("%d\n",q);                                       //
}

inline bool comp(punct i, punct j)
{
    if(i.tg<0&&j.tg>=0) return 0;
    if(i.tg>=0&&j.tg<0) return 1;
    if(i.tg!=j.tg) return(i.tg<j.tg);
    else return (sqrt((i.y-a[q].y)*(i.y-a[q].y)+(i.x-a[q].x)*(i.x-a[q].x))<sqrt((j.y-a[q].y)*(j.y-a[q].y)+(j.x-a[q].x)*(j.x-a[q].x)));
}

void tang()
{
    int i;
    for(i=1; i<=n; ++i)
    {
        if(i!=q)
        {
            if(a[i].x!=a[q].x) a[i].tg=(a[i].y-a[q].y)/(a[i].x-a[q].x);
            else a[i].tg=1000000001;
        }
        else  a[i].tg=0;
        //printf("%f\n",a[i].tg);                                     //
    }
    sort(a+1,a+n+1,comp);
}

inline bool ok(int p0, int p1, int p2)
{
    return(((a[p1].x-a[p0].x)*(a[p2].y-a[p0].y)-(a[p2].x-a[p0].x)*(a[p1].y-a[p0].y))>=0);
}

void generare()
{
    int i/*,p1=1,p2=2,p=1*/;
    for(i=3; i<=n; ++i)
    {
        if(ok(/*p1,p2,*/s[nr-1],s[nr],i))
        {
            /*p=p1;
            p1=p2;
            p2=i;*/
            s[++nr]=i;
        }
        else
        {
            //p2=p1;
            //p1=p;
            //--i;
            --nr;
            while(!ok(s[nr-1],s[nr],i))
            {
                --nr;
            }
            s[++nr]=i;
        }
    }
}

int main()
{
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);
    cit();
    aleg();
    tang();
    s[1]=1;
    s[2]=2;
    generare();
    afis();
    return 0;
}