Pagini recente » Cod sursa (job #1451028) | Cod sursa (job #2022514) | Cod sursa (job #1283324) | Cod sursa (job #941451) | Cod sursa (job #1848945)
/*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;
}