Pagini recente » Cod sursa (job #654630) | Cod sursa (job #2728812) | Cod sursa (job #3186819) | Cod sursa (job #453011) | Cod sursa (job #481941)
Cod sursa(job #481941)
#include <fstream>
#include <vector>
#include <algorithm>
#include <iostream>
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;
int index;
vector<point> crescator;
vector<point> descrescator;
vector<point>::iterator iter;
fin >> n;
for( int i = 0; i < n; i++ )
{
point punct;
fin >> punct.x >> punct.y;
crescator.push_back(punct);
}
fin.close();
sort( crescator.begin(), crescator.end(), comparison );
descrescator.resize(crescator.size());
reverse_copy(crescator.begin(), crescator.end(), descrescator.begin());
for( iter = descrescator.begin() + 1; iter != descrescator.end(); iter++ )
{
crescator.push_back( *iter );
}
index = 1;
do
{
iter = crescator.begin() + index;
double a = crescator[index - 1].y - crescator[index + 1].y;
double b = crescator[index + 1].x - crescator[index - 1].x;
double c = crescator[index + 1].y * crescator[index - 1].x -
crescator[index + 1].x * crescator[index - 1].y;
long double ecuatie = a * crescator[index].x +
b * crescator[index].y +
c;
if( ecuatie > 0 )
{
crescator.erase( iter );
if( index > 1 )
{
index--;
}
}
else if( index < crescator.size() - 1 )
{
index++;
}
}while( index < crescator.size() - 1 );
crescator.pop_back();
fout.precision(16);
fout << crescator.size() << "\n";
for( iter = crescator.begin(); iter != crescator.end(); iter++ )
{
fout << (*iter).x << " " << (*iter).y << "\n";
}
fout.close();
return 0;
}