Pagini recente » Cod sursa (job #2999491) | Cod sursa (job #1480697) | Cod sursa (job #1906453) | Cod sursa (job #348677) | Cod sursa (job #480182)
Cod sursa(job #480182)
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
struct point
{
double x;
double y;
};
bool comparison( point A, point B )
{
if( A.y < B.y || ( A.y == B.y && A.x < B.x ) )
return true;
else
return false;
}
int main()
{
ifstream fin( "infasuratoare.in" );
ofstream fout( "infasuratoare.out" );
int n;
vector<point> puncte;
fin >> n;
for( int i = 0; i < n; i++ )
{
point punct;
fin >> punct.x >> punct.y;
puncte.push_back(punct);
}
sort( puncte.begin(), puncte.end(), comparison );
fin.close();
vector<point> infasuratoare;
infasuratoare.push_back( puncte[0] );
infasuratoare.push_back( puncte[1] );
// fout << puncte[0].x << " " << puncte[0].y << " added\n";
// fout << puncte[1].x << " " << puncte[1].y << " added\n";
for( int i = 2; i < n; i++ )
{
double ecuatie, a, b, c;
do
{
int index = infasuratoare.size() - 1;
a = infasuratoare[index - 1].y - infasuratoare[index].y;
b = infasuratoare[index].x - infasuratoare[index - 1].x;
c = infasuratoare[index].x * infasuratoare[index - 1].y -
infasuratoare[index].y * infasuratoare[index - 1].x;
ecuatie = a * puncte[i].x + b * puncte[i].y + c;
if( ecuatie > 0 )
{
// fout << infasuratoare[index].x << " " << infasuratoare[index].y << " removed\n";
infasuratoare.pop_back();
}
}while( ecuatie > 0 );
// fout << puncte[i].x << " " << puncte[i].y << " added\n";
infasuratoare.push_back( puncte[i] );
}
for( int i = n - 2; i >= 0; i-- )
{
double ecuatie, a, b, c;
do
{
int index = infasuratoare.size() - 1;
a = infasuratoare[index - 1].y - infasuratoare[index].y;
b = infasuratoare[index].x - infasuratoare[index - 1].x;
c = infasuratoare[index].x * infasuratoare[index - 1].y -
infasuratoare[index].y * infasuratoare[index - 1].x;
ecuatie = a * puncte[i].x + b * puncte[i].y + c;
if( ecuatie < 0 )
{
// fout << infasuratoare[index].x << " " << infasuratoare[index].y << " removed\n";
infasuratoare.pop_back();
}
}while( ecuatie < 0 );
// fout << puncte[i].x << " " << puncte[i].y << " added\n";
infasuratoare.push_back( puncte[i] );
}
fout << infasuratoare.size() - 1 << "\n";
for( int i = infasuratoare.size() - 1; i > 0; i-- )
fout << infasuratoare[i].x << " " << infasuratoare[i].y << "\n";
fout.close();
return 0;
}