Pagini recente » Cod sursa (job #510451) | Borderou de evaluare (job #753669) | Cod sursa (job #1548337) | Cod sursa (job #618376) | Cod sursa (job #481938)
Cod sursa(job #481938)
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
#include <iomanip>
using namespace std;
struct point
{
double x;
double y;
};
bool comparison( const point& A, const point& B )
{
if( A.x < B.x || ( A.x == B.x && A.y < B.y ) )
return true;
else
return false;
}
bool turnsRight( const point& A, const point& B, const point& C )
{
double a = A.y - B.y;
double b = B.x - A.x;
double c = A.x * B.y - B.x * A.y;
double ecuation = a * C.x + b * C.y + c;
return ( ecuation < 0 );
}
int main()
{
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
vector<point> puncte;
vector<point>::iterator iter;
int n;
fin >> n;
for( int i = 0; i < n; i++ )
{
point punct;
fin >> punct.x >> punct.y;
puncte.push_back( punct );
}
fin.close();
sort( puncte.begin(), puncte.end(), comparison );
vector<point> stiva;
stiva.push_back( puncte[0] );
stiva.push_back( puncte[1] );
for( int i = 2; i < puncte.size(); i++ )
{
while( stiva.size() > 1 && turnsRight( stiva[stiva.size() - 2], stiva[stiva.size() - 1], puncte[i] ))
stiva.pop_back();
stiva.push_back( puncte[i] );
}
for( int i = puncte.size() - 2; i >= 0 ; i-- )
{
while( stiva.size() > 1 && turnsRight( stiva[stiva.size() - 2], stiva[stiva.size() - 1], puncte[i] ))
stiva.pop_back();
stiva.push_back( puncte[i] );
}
stiva.pop_back();
fout << stiva.size() << "\n";
for( int i = 0; i < stiva.size(); i++ )
{
fout << setprecision(6) << stiva[i].x << " " << stiva[i].y << "\n";
}
return 0;
}