Cod sursa(job #1540014)

Utilizator razvanxdVancea Cosmin Razvan razvanxd Data 1 decembrie 2015 22:26:07
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 5.28 kb
/*
Infasuratoare convexa:

Implementare algoritm:
https://drive.google.com/file/d/0Bxh__ul1ji8IZVhqSTVYZk9Pc190MlRfUXc1aERKSC1teXc0/view?usp=sharing
Exceptie: ordonarea se face dupa abscisa si ordonata; nu invers
*/

#include <iostream>
#include <fstream>
#include <algorithm> // sort
#include <cmath> // acos, sqrt
#include <vector>
#include <iomanip>

using namespace std;

struct punct {double x, y, ang_pol;};

vector<punct> puncte;
vector<punct> stiva; // va contine punctele poligonului in ordine invers-trigonometrica
punct min_punct;
unsigned long min_p = 0, n;
double dist_ipot, dist_cat, dist1, dist2;


double E(punct p1, punct p2, punct p)
{
    return p1.x*p2.y + p2.x*p.y + p.x*p1.y - p1.x*p.y - p2.x*p1.y - p.x*p2.y;
}

bool sort_puncte(punct p1, punct p2)
{
    if(p1.ang_pol < p2.ang_pol) return 1; // se muta p2 in locul lui p1 daca unghiul polar al lui p2 este mai mic
    if(p1.ang_pol == p2.ang_pol)
    {
        dist1 = (p1.x-puncte[min_p].x)*(p1.x-puncte[min_p].x)+(p1.y-puncte[min_p].y)*(p1.y-puncte[min_p].y);
        dist2 = (p2.x-puncte[min_p].x)*(p2.x-puncte[min_p].x)+(p2.y-puncte[min_p].y)*(p2.y-puncte[min_p].y);

        if(dist1 < dist2) return 1; // la unghiuri egale se muta doar daca dist AP2 > dist AP1
        else if(dist1 == dist2)
        {
            if(p1.y > p2.y) return 1; // la distante egale se ordoneaza dupa y desc. (???)
        }
    }
    return 0;
}

int main()
{
    ifstream fin("infasuratoare.in");
    fin >> n;

    for(unsigned long i = 0; i < n; ++i)
    {
        fin >> min_punct.x >> min_punct.y;
        min_punct.ang_pol = -1;
        puncte.push_back(min_punct); // adaug punctul citit in vector

        if(puncte[i].x < puncte[min_p].x) min_p = i;
        else if(puncte[i].x == puncte[min_p].x && puncte[i].y < puncte[min_p].y) min_p = i;
    }
    fin.close();

    min_punct.x = puncte[min_p].x;
    min_punct.y = puncte[min_p].y;

    puncte.erase(puncte.begin() + min_p); // mut punctul cu coordonata x minima (si y ?) pe pozitia 0 in vector
    puncte.insert(puncte.begin(), min_punct);

    for(unsigned long i = 1; i < puncte.size(); ++i)
    {
        /*
                                    M2(i.x, i.y)
                                        x
                                       /|
                                      / |
                                     /  |
                      dist_ipot =>  /   |
                                   /    |
                                  /     |
                                 /      |
                                /ang    |
                               x--------x
                  M1(min.x, min.y)  ^  M3(min.x, i.y)
                                    |
                                    |
                                    |
                                dist_cat
        */

        dist_ipot = sqrt((puncte[i].x-min_punct.x)*(puncte[i].x-min_punct.x)+(puncte[i].y-min_punct.y)*(puncte[i].y-min_punct.y)); // M1M2
        dist_cat = min_punct.y-puncte[i].y; // M1M3
        if(dist_cat < 0) dist_cat = -dist_cat; // distanta nu poate fi negativa

        if(puncte[i].y < min_punct.y) dist_cat = -dist_cat; // daca punctul M2 se afla sub M1, atunci cos trebuie sa fie negativ (IMPORTANT!) (???)
        puncte[i].ang_pol = acos(dist_cat/dist_ipot); // unghiul polar aflat prin arccos(cos(ang))
    }

    sort(puncte.begin()+1, puncte.end(), sort_puncte); // sortez punctele CU EXCEPTIA celui de pe pozitia 0

    for(unsigned long i = puncte.size()-1; i > 1; --i) // se sterg punctele care au acelasi unghi polar, ramanand doar cel mai distantat de M1
    {
        if(puncte[i].ang_pol == puncte[i-1].ang_pol)
        {
            dist1 = (puncte[i].x-puncte[min_p].x)*(puncte[i].x-puncte[min_p].x)+(puncte[i].y-puncte[min_p].y)*(puncte[i].y-puncte[min_p].y);
            dist2 = (puncte[i-1].x-puncte[min_p].x)*(puncte[i-1].x-puncte[min_p].x)+(puncte[i-1].y-puncte[min_p].y)*(puncte[i-1].y-puncte[min_p].y);

            if(dist1 != dist2) puncte.erase(puncte.begin() + i); // in cazul in care punctele au distanta egala si unghiul egal, atunci nu se mai sterg (???)
        }
    }

    stiva.push_back(puncte[0]); // se adauga primele 3 puncte in stiva
    stiva.push_back(puncte[1]);
    stiva.push_back(puncte[2]);

    for(unsigned long i = 3; i < puncte.size(); ++i) // se adauga urmatoarele puncte
    {
        stiva.push_back(puncte[i]); // adaugare
        while(E(stiva[stiva.size()-1-2], stiva[stiva.size()-1-1], stiva[stiva.size()-1]) > 0) // se verifica daca ultimul punct adaugat ANULEAZA CONVEXITATEA (se afla in stanga vectorului determinat de antepenultimul si penultimul punct (cu varful in penultimul))
        {// de ce stanga anuleaza convexitatea? pt. ca punctele sunt ordonate in vector crescator dupa unghiul polar care CRESTE cu cat punctul se afla mai sus decat punctul M1, asadar
            stiva.erase(stiva.end()-1-1); // se sterge penultimul punct din vector pana cand SE PASTREAZA CONVEXITATEA cu ultimul punct
        }
    }


    ofstream fout("infasuratoare.out");
    fout << stiva.size() << endl;
    for (unsigned i = stiva.size(); i-- > 0; )
    {
        fout << fixed << setprecision(6) << stiva[i].x << ' ' << stiva[i].y << endl;
    }
    fout.close();
    return 0;
}