Pagini recente » Cod sursa (job #379817) | Cod sursa (job #1863418) | Cod sursa (job #2830708) | Cod sursa (job #963392) | Cod sursa (job #1870460)
#include <iostream>
#include <fstream>
#include <stack>
#include <vector>
#include <algorithm>
#include <iomanip>
using namespace std;
#define x first
#define y second
#define punct pair < double , double >
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int n , i , poz , nr;
pair < double, double > minn;
vector < pair < double , double > > v;
punct minnn;
punct st[120001];
double panta ( punct a, punct b , punct c )
{
return ( b.x - a.x )*(c.y - a.y) - (b.y-a.y)*(c.x-a.x) ;
}
bool criteriu ( punct a, punct b )
{
return panta(v[1],a,b)<0;
}
int main()
{
f >> n;
v = vector < pair < double , double > > (n+1);
f >> v[1].x >> v[1].y;
minn = v[1];
for ( i = 2 ; i <= n ; i++ )
{
f >> v[i].x >> v[i].y;
if ( minn.x > v[i].x or (minn.x==v[i].x and minn.y > v[i].y))
minn = v[i] , poz = i;
}
swap(v[1],v[poz]);
sort(v.begin()+2,v.end(),criteriu);
st[1] = v[1];
st[2] = v[2];
nr = 2;
for ( i = 3; i <= n ; i++ )
{
while( nr >=2 and panta(st[nr-1],st[nr],v[i]) > 0 )
{
--nr;
}
st[++nr] = v[i];
}
freopen("infasuratoare.out","w",stdout);
printf( "%d\n", nr );
for ( i = nr ; i >= 1 ; i-- )
{
printf( "%.9f %.9f\n" , st[i].x, st[i].y);
}
return 0;
}