Pagini recente » Cod sursa (job #2779970) | Cod sursa (job #2048029) | Cod sursa (job #1350517) | Cod sursa (job #2121498) | Cod sursa (job #1785156)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
#define MAX_NUMAR_PUNCTE 120005
using namespace std;
vector<pair<double, double>> puncte(MAX_NUMAR_PUNCTE, make_pair(0.0, 0.0));
vector<pair<double, double>> stiva(MAX_NUMAR_PUNCTE, make_pair(0.0, 0.0));
int numarPuncte;
int varfStiva;
void CitireInput()
{
ifstream in("infasuratoare.in");
in>> numarPuncte;
for( int i = 1; i<=numarPuncte; ++i )
{
in>> puncte[i].first>> puncte[i].second;
}
in.close();
}
int AlegerePunctStart()
{
int indexElementMinim = 1;
for( int i = 2; i<=numarPuncte; ++i )
{
if( puncte[i] < puncte[indexElementMinim] )
{
indexElementMinim = i;
}
}
return indexElementMinim;
}
double ArieTriunghi(pair<double, double> punct1, pair<double, double> punct2,
pair<double, double> punct3)
{
return punct1.first*punct2.second + punct2.first*punct3.second +
punct3.first*punct1.second - punct3.first*punct2.second -
punct1.first*punct3.second - punct2.first*punct1.second;
}
bool CompararePuncte(pair<double, double> punct1, pair<double, double> punct2)
{
return ArieTriunghi(puncte[1], punct1, punct2) < 0;
}
void SortarePuncte()
{
int indexElementMinim = AlegerePunctStart();
swap(puncte[1], puncte[indexElementMinim]);
sort(puncte.begin() + 2, puncte.begin() + numarPuncte + 1, CompararePuncte);
}
void ConvexHull()
{
SortarePuncte();
stiva[1] = puncte[1];
stiva[2] = puncte[2];
varfStiva = 2;
for( int i = 3; i<=numarPuncte; ++i )
{
while( varfStiva >= 2 && ArieTriunghi(stiva[varfStiva - 1], stiva[varfStiva], puncte[i]) > 0 )
{
--varfStiva;
}
stiva[++varfStiva] = puncte[i];
}
}
void AfisareRezultat()
{
ofstream out("infasuratoare.out");
out<< fixed<< varfStiva<< "\n";
for( int i = varfStiva; i >= 1; --i )
{
out<< setprecision(12)<< stiva[i].first<<" "<< stiva[i].second<< "\n";
}
out.close();
}
int main()
{
CitireInput();
ConvexHull();
AfisareRezultat();
return 0;
}