Pagini recente » Cod sursa (job #2596307) | Cod sursa (job #407383) | Cod sursa (job #2860269) | Cod sursa (job #654588) | Cod sursa (job #481939)
Cod sursa(job #481939)
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
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();
freopen("infasuratoare.out", "w", stdout);
printf("%d\n", stiva.size());
for( int i = 0; i < stiva.size(); i++ )
{
printf("%lf %lf\n", stiva[i].x, stiva[i].y );
}
return 0;
}