Cod sursa(job #1627373)

Utilizator QQQ1911Vodita Stefan QQQ1911 Data 3 martie 2016 16:56:24
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.84 kb
#include <stdio.h>
#include <algorithm>
#include <math.h>
using namespace std;

int n,q,nr=2,s[120001];
struct punct
{
    float 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;
    float 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;
        }
    }
}

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)
        a[i].tg=(a[i].y-a[q].y)/(a[i].x-a[q].x);
    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,i))
        {
            ++nr;
            p=p1;
            p1=p2;
            p2=i;
            s[nr]=i;
        }
        else
        {
            p2=p1;
            p1=p;
            --i;
            --nr;
        }
    }
}

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;
}