Cod sursa(job #1029006)

Utilizator R4DIC4LTeodorescu Oana Maria R4DIC4L Data 14 noiembrie 2013 21:52:02
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 3.5 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <utility>
#include <iomanip>
std::ifstream f("infasuratoare.in");
std::ofstream g("infasuratoare.out");
int n;
typedef struct punct
{
    double x;
    double y;
    bool operator <(const punct& p) const
    {
        return (x < p.x || (x == p.x && y < p.y) );
    }
} punct_obj;

punct *punctXY;
///       | x1  y1  1 |
/// det = | x2  y2  1 |
///       | x3  y3  1 |
/// daca det < 0 => P3(x3, y3) in dreapta (jos) vectorului P1P2
/// daca det > 0 => P3(x3, y3) in stanga (sus) vectorului P1P2
double det (punct pct1, punct pct2, punct pct3)
{
    return (pct1.x*pct2.y + pct2.x*pct3.y + pct3.x*pct1.y
            - pct3.x*pct2.y - pct1.x*pct3.y - pct2.x*pct1.y);
}
int main ()
{
    f >> n;
    punctXY = new punct[n];
    f >> punctXY[0].x >> punctXY[0].y;
    int maxX = punctXY[0].x ,minX = punctXY[0].y, indiceMax = 0, indiceMin = 0;
    /// determina punctele de extrem dupa x (abscisa minima si maxima)
    /// P_min : x = minX, indice = indiceMin; P_max : x = maxX, indice = indiceMax
    for (int i = 1; i < n; ++ i)
    {
        f >> punctXY[i].x >> punctXY[i].y;
        if (punctXY[i].x < minX)
        {
            minX = punctXY[i].x;
            indiceMin = i;
        }
        else
            if (punctXY[i].x > maxX)
            {
                maxX = punctXY[i].x;
                indiceMax = i;
            }
    }
    /// separa multimea S in S_inf (stanga) si S_sup (dreapta)
    std::vector <punct> sInf;
    std::vector <punct> sSup;
    sInf.push_back(punctXY[indiceMin]);
    sSup.push_back(punctXY[indiceMin]);
    for (int i = 0; i < n; ++ i)
        if (i != indiceMax && i != indiceMin)
        {
            if (det(punctXY[indiceMin], punctXY[indiceMax], punctXY[i]) < 0)
            {
                sInf.push_back(punctXY[i]);
            }
            else
            {
                sSup.push_back(punctXY[i]);
            }
        }
    sInf.push_back(punctXY[indiceMax]);
    sSup.push_back(punctXY[indiceMax]);
    /// sorteaza S_inf si S_sup (sort din STL)
    std::sort(sInf.begin() + 1, sInf.end() - 1);
    std::sort(sSup.begin() + 1, sSup.end() - 1);
    /// creeaza infasuratoarea convexa pentru S_inf si S_sup
    int i = 0;
    /// infasuratoare convexa pentru s_sup
    while (i + 2 < sSup.size())
    {
        if (det (sSup[i], sSup[i + 2], sSup[i + 1]) > 0)
            ++ i;
        else
            sSup.erase(sSup.begin() + i + 1);
    }
    i = 0;
    /// infasuratoare convexa pentru s_inf
    indiceMin = 0;
    punct p = sInf[0];
    while (i + 2 < sInf.size())
    {
        if (det (sInf[i], sInf[i + 2], sInf[i + 1]) < 0)
        {
            ++ i;
            if (sInf[i].y < p.y || sInf[i].y == p.y && sInf[i].x < p.x)
            {
                p = sInf[i];
                indiceMin = i;
            }
        }
        else
            sInf.erase(sInf.begin() + i + 1);
    }

    /// afiseaza in sens trigonometric punctele din infasuratoarea convexa
    g << sInf.size() + sSup.size() - 2 << "\n";
    for (int i = indiceMin; i < sInf.size(); ++ i)
        g << std::fixed << std::setprecision(6) << sInf[i].x << " " << sInf[i].y << "\n";
    for (int i = 0; i < indiceMin; ++ i)
        g << std::fixed << std::setprecision(6) << sInf[i].x << " " << sInf[i].y << "\n";
    for (int i = sSup.size() - 2; i > 0; -- i)
        g << std::fixed << std::setprecision(6) << sSup[i].x << " " << sSup[i].y << "\n";
    return 0;
}