Cod sursa(job #1372253)

Utilizator bullseYeIacob Sergiu bullseYe Data 4 martie 2015 12:27:31
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.62 kb
#include <cstdio>
#include <algorithm>
#include <cmath>
#define NMAX 10010
#define INF 2000000000
using namespace std;

struct pack{
    double x, y;
    double u, r;
};
struct pack P[NMAX], S[NMAX];

int n, sol;

void citire ();
void rez ();
void ordoneaza ();
int pi (struct pack, struct pack, struct pack);
bool comp (struct pack, struct pack);
void afisare();

int main()
{
    citire();
    rez();
    afisare();
    return 0;
}

void citire()
{
    int i;
    FILE*fin=fopen ("infasuratoare.in", "r");
    fscanf(fin, "%d", &n);
    for (i=1; i<=n; ++i)
        fscanf(fin, "%lf %lf", &P[i].x, &P[i].y);
    fclose(fin);
    return;
}

void rez()
{
    int i, vf, prod;
    ordoneaza();
    S[1]=P[1]; S[2]=P[2];
    vf=2;
    for (i=3; i<=n; ++i)
    {
        prod=pi(S[vf-1], S[vf], P[i]);
        if (!prod)//atunci S[vf] si P[i] au aceleasi unghiuri polare fata de P[1]
        {
            //il retin doar pe cel mai indepartat, adica P[i]
            --vf;
            S[++vf]=P[i];
        }
            else
            if (prod>0)//intoarcere la stanga
                S[++vf]=P[i];
                else
                {
                    //nu-i bun
                    while (vf>1 && prod<=0)
                    {
                        --vf;
                        prod=pi(S[vf-1], S[vf], P[i]);
                    }
                    S[++vf]=P[i];
                }
    }
    sol=vf;
    return;
}

void ordoneaza()
{
    struct pack aux;
    int i, ymin=INF, xmin=INF, minimus;
    for (i=1; i<=n; ++i)
        if (P[i].y<ymin || (ymin==P[i].y && P[i].x<xmin))
            {
                minimus=i;
                ymin=P[i].y;
                xmin=P[i].x;
            }
    aux=P[1];
    P[1]=P[minimus];
    P[minimus]=aux;
    for (i=2; i<=n; ++i)
    {
        P[i].u=atan((double)(P[i].y-P[1].y)/(P[i].x-P[1].x));
        P[i].r=sqrt((double)(P[i].y-P[1].y)*(P[i].y-P[1].y)+(P[i].x-P[1].x)*(P[i].x-P[1].x));
    }
    sort (P+2, P+n+1, comp);
    return;
}

bool comp (struct pack a, struct pack b)
{
    return a.u<b.u || (a.u==b.u && a.r<b.r);
}

int pi (struct pack a, struct pack b, struct pack c)
{
    return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
}
//returneaza o val. pozitiva daca in b-c se face o intoarcere la stanga
//respectiv o val. negativa daca in b-c se face o intoarcere la dreapta

void afisare()
{
    int i;
    FILE*fout=fopen ("infasuratoare.out", "w");
    fprintf(fout, "%d\n", sol);
    for (i=1; i<=sol; ++i)
        fprintf(fout, "%lf %lf\n", S[i].x, S[i].y);
    fclose(fout);
    return;
}