Cod sursa(job #890396)

Utilizator romircea2010FMI Trifan Mircea Mihai romircea2010 Data 25 februarie 2013 01:07:28
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.35 kb
// infasuratoarea ma-sii
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cstdio>
#include <cmath>

using namespace std;

int n, pos, vf;
struct Punct
{
    double x, y;
};
Punct a[120010], st[120010];

inline void Read()
{
    ifstream f ("infasuratoare.in");
    f>>n;
    int i;
    double x, y;
    pos = 1;
    for (i=1; i<=n; i++)
    {
        f>>x>>y;
        a[i].x = x;
        a[i].y = y;
        if (y < a[pos].y || (y == a[pos].y && x < a[pos].x))
            pos = i;
    }
    f.close();
}

inline double Dist(const Punct A)
{
    return (A.x-a[1].x)*(A.x-a[1].x)+(A.y-a[1].y)*(A.y-a[1].y);
}

inline bool cmp (const Punct A, const Punct B)
{
    //y2 - y0 / x2 - x0 < y1 - y0 / x1 - x0
    //y2 - y0 * x1 - x0 < y1 - y0 * x2 - x0
    double p1, p2;
    p1 = (B.y - a[1].y)*(A.x - a[1].x);
    p2 = (A.y - a[1].y)*(B.x - a[1].x);
    if (p1 == p2) // daca au aceleasi distanta le sortez crescator dupa distanta pana la punctul din stanga-jos
        return Dist(A) < Dist(B);
    return p1 < p2;
}

inline double Intoarcere(const Punct A, const Punct B, const Punct C)
{
    // A.x A.y 1
    // B.x B.y 1
    // C.x C.y 1
    return A.x * B.y + B.x * C.y + A.y * C.x - B.y * C.x - A.y * B.x - A.x * C.y;
}

inline void Infasoara()
{
    Punct aux;
    aux = a[1];
    a[1] = a[pos];
    a[pos] = aux;
    sort(a+2, a+n+1, cmp);
    vf++;
    st[vf] = a[1];
    vf++;
    st[vf] = a[2];
    int i;
    double o;
    for (i = 3; i<=n; i++)
    {
        o = Intoarcere (st[vf-1], st[vf], a[i]);
        if (o == 0.0) // puncte colineare
            st[vf] = a[i];
        else
            if (o < 0.0) // daca face intoarecere la stanga, in sens trigonometric il bag
                st[++vf] = a[i];
            else
            {
                while (vf >= 2 && o > 0.0) // daca face intoarcere la dreapta scot pana face intoarcere la stanga.
                {
                    vf--;
                    o = Intoarcere(st[vf-1], st[vf], a[i]);
                }
                st[++vf] = a[i];
            }
    }
}

inline void Write()
{
    freopen ("infasuratoare.out", "w", stdout);
    printf ("%d\n", vf);
    while (vf)
        printf ("%lf %lf\n", st[vf].x, st[vf].y), vf--;
}

int main()
{
    Read();
    Infasoara();
    Write();
    return 0;
}