Cod sursa(job #1848945)

Utilizator mariusmagureanmagurean marius mariusmagurean Data 16 ianuarie 2017 21:20:25
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 3.8 kb
/*Infasuratoarea convexa in O(N*H)
Metoda Jarvis sau infasurarea pachetului

Se gaseste cel mai din stanga punct. El, sigur, va face parte din infasuratoare.
Se cauta apoi punctul care face cel mai mare unghi dintre dreapta suport a lui cu punctul anterior si o paralela la OX
ce trece prin punctul anterior.
Apoi se cauta un punct care face cel mai mare punct intre dreapta suport a punctului curent si noul punct cu dreapta
suport a punctului curent si cel anterior
Calcularea unghiului se realizeaza cu functia atan2, care calc arctg(y/x). La noi y va fi diferenta ordonatelor punctelor, iar x
diferenta absciselor.
Se repeta procedeul cu ultimul punct gasit si un nou punct pana ajungem de unde am pornit.
Explicarea complexitatii. Pentru primul punct de pe infasuratoare se fac n-1 cautari, ptr al doilea n-2,
iar ptr al h-lea, n-h.
Citirea, calcularea punctului celui mai din stanga si functia reverse au timp liniar, deci intreg algoritmul are O(N*H).
*/

#include<fstream>
#include<cmath>
#include<vector>
#include<iomanip>
#include<algorithm>

#define dim 120005

using namespace std;

vector<int>v;
double x[dim],y[dim];
bool in[dim],ok;
int n,h;

void citire()
{
    ifstream fin("infasuratoare.in");
    fin>>n;
    int i;
    for(i=1;i<=n;i++)
        fin>>x[i]>>y[i];
    fin.close();
}

int main()
{
    citire();
    ofstream fout("infasuratoare.out");
    //calculam cel mai stanga punct (cu x-ul cel mai mic)
    //variabila mic retine indicele elementului celui mai din stanga
    int i,mic=1,c,poz;
    double unghi,maxU,uAnt;
    for(i=2;i<=n;i++)
        if(x[i]<x[mic])
            mic=i;
    //in[i]=1 daca i este pe infasuratoare si 0 contrar
    //variabila c va retine nodul curent din infasuratoare
    //pornim de la mic, el sigur va fi pe infasuratoare
    c=mic;
    //folosesc ok pentru a intra prima data in repetitie
    //apoi voi continua cat timp nodul curent este diferit de cel de pornire
    ok=1;
    //unghiul anterior este retinut in uAnt
    uAnt=0;
    while(ok==1 || c!=mic)
    {
        ok=0;
        v.push_back(c);
        //poz va retine pozitia urmatorului unghi, pozitie calculata, presupun ca este c la inceput
        poz=c;
        //unghiurile sunt masurate in radiani deci vor fi in intervalul -pi pi
        maxU=10000;
        //parcurgem toate punctele ramase
        for(i=1;i<=n;i++)
        {
            //ne intereseaza punctele care nu au fost folosite si care nu sunt punctul de pornire
            if(in[i]==1 || i==c)
                continue;
            unghi=atan2((x[i]-x[c]),(y[i]-y[c]));
            //daca unghiul este negativ adunam 2*pi
            if(unghi<0)
                unghi+=2*M_PI;
            //acum scadem din unghi, unghiul anterior, fiindca unghi reprezinta unghiul dintre dreapta suport si paralela la OX
            unghi-=uAnt;
            //iarasi verificam daca este negativ unghiul
            if(unghi<0)
                unghi+=2*M_PI;
            //acum unghi este corect calculat, testam daca e cel care face cea mai mare intoarcere
            if(maxU>unghi)
            {
                maxU=unghi;
                poz=i;
            }
        }
        //dupa ce l am gasit actualizam unghiul anterior tinand cont ca va fi situat sub unghiul curent
        uAnt=atan2(-(x[c]-x[poz]),-(y[c]-y[poz]));
        //daca e negativ, adunam 2*Pi
        if(uAnt<0)
            uAnt+=2*M_PI;
        //actualizam pozitia curenta
        c=poz;
        //marcam punctul gasit ca folosit si il introducem in vector
        in[c]=1;
    }
    //punctele obtinute sunt in ordine invers trigonometrica, le inversam in vectorul v
    reverse(v.begin(),v.end());
    h=v.size();
    fout<<h<<"\n";
    for(i=0;i<h;i++)
        fout<<setprecision(6)<<x[v[i]]<<" "<<y[v[i]]<<"\n";
    return 0;
}