Cod sursa(job #953089)

Utilizator gabrielinelusGabriel-Robert Inelus gabrielinelus Data 24 mai 2013 19:52:59
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.61 kb
#include <cstdio>
#include <climits>
#include <algorithm>
FILE *f=fopen("infasuratoare.in","r");
FILE *g=fopen("infasuratoare.out","w");
#define INF 999999
#define mil 1000000
using namespace std;
struct points
{
    double i,j;
    double panta();
    friend double operator!=(points A,points B)
    {
        if(A.i==B.i&&A.j==B.j)return 0;
        return 1;
    }
}p[100],pmins,pmind,pjos[100],psus[100],HULL[100];
int n,njos,used[100],nsus,nHULL,usedj[100],useds[100];
bool cmp(points p1,points p2)// functia magica
{
    if(p1.i<p2.i)return 1;
    if(p1.i==p2.i)
        if(p1.j<p2.j)return 1;
    return 0;
}
double panta (points A,points B)
{
    if(A.i==B.i)return INF;
    return (1.0*(A.j-B.j)/(A.i-B.i));
}
void partajare()
{
    double limita;
    njos=1;
    limita=panta(pmins,pmind);
    pjos[njos++]=pmins;
    for(int i=2;i<=n;++i)
        if(!used[i])
            if(limita>panta(pmins,p[i]))
            {
                pjos[njos++]=p[i];
                used[i]=1;
            }
    pjos[njos++]=pmind;
    nsus=1;
    for(int i=2;i<=n;++i)
        if(!used[i])
            psus[nsus++]=p[i];
}
void solve()
{
    int i=1,j,poz;
    HULL[i]=pmins;
    double min=INF;
    while(HULL[i]!=pmind)
    {
        min=INF;
        for(j=2;j<njos;++j)
            if(!usedj[j])
            if(panta(HULL[i],pjos[j])<min)
                {
                    poz=j;
                    min=panta(HULL[i],pjos[j]);
                }
        HULL[++i]=pjos[poz];
        usedj[poz]=1;
    }
    for(j=1;j<nsus;++j)
        if(panta(HULL[i],psus[j])==INF)
            {HULL[++i]=psus[j];useds[j]=1;break;}
    while(HULL[i]!=HULL[i-1])
    {
        min=INF;
        for(j=1;j<nsus;++j)
            if(!useds[j])
            if(panta(HULL[i],psus[j])<min&&HULL[i].i>=psus[j].i)
            {
                poz=j;
                min=panta(HULL[i],psus[j]);
            }
        HULL[++i]=psus[poz];
        useds[poz]=1;
    }
    fprintf(g,"%d\n",i-1);
    for(int k=2;k<i;++k)
        fprintf(g,"%lf %lf\n",HULL[k].i-mil,HULL[k].j-mil);
    fprintf(g,"%lf %lf\n",HULL[1].i-mil,HULL[1].j-mil);
}
int main()
{
    int i;
    fscanf(f,"%d",&n);
    for(i=1;i<=n;i++)
    {
        fscanf(f,"%lf%lf",&p[i].i,&p[i].j);
        p[i].i+=mil;
        p[i].j+=mil;
    }
    sort(p+1,p+n+1,cmp);
    pmins=p[1];
    used[1]=1;
    for(i=n;i>=0;--i)
        if(p[i-1].i!=p[i].i)break;
    pmind=p[i];
    used[i]=1;
    //printf("extrem stanga :%d %d \nextrem dreapta :%d %d",pmins.i,pmins.j,pmind.i,pmind.j);
    partajare();
    solve();
    return 0;
}