Pagini recente » Cod sursa (job #2649614) | Cod sursa (job #184983) | Cod sursa (job #185539) | Cod sursa (job #1775158) | Cod sursa (job #2157979)
#include <fstream>
#include <algorithm>
#include <iomanip>
#define N 120000
using namespace std;
ifstream fin ("infasuratoare.in");
ofstream fout ("infasuratoare.out");
struct plan
{
double x,y;
};
int n;
plan sv[N], v[N];
inline int orientation ( plan a, plan b, plan c )
{
double r1, r2;
r1 = (b.x - a.x) * (c.y - b.y);
r2 = (c.x - b.x) * (b.y - a.y);
if ( r1 > r2 )
return 1;
else
return 0;
}
bool cmp ( plan b, plan a )
{
return orientation( v[0], a, b );
}
void print ();
int main()
{
ios::sync_with_stdio (false);
int i, h, pos = 0;
fin >> n >> v[0].x >> v[0].y;
for ( i = 1; i < n; ++i )
{
fin >> v[i].x >> v[i].y;
if ( v[i].y < v[pos].y )
pos = i;
else if ( v[i].y == v[pos].y && v[i].x < v[pos].x )
pos = i;
}
swap ( v[0], v[pos] );
sort ( v + 1, v + n, cmp );
//print();
sv[0] = v[0], sv[1] = v[1];
h = 1;
for ( i = 2; i < n; ++i )
{
while ( orientation( sv[h - 1], sv[h], v[i] ) == 1 && h > 1 )
--h;
sv[++h] = v[i];
}
fout << h + 1 << '\n';
fout << fixed << setprecision (12) << sv[0].x << " " << sv[0].y << '\n';
for ( ; h > 0; --h )
fout << fixed << setprecision (12) << sv[h].x << " " << sv[h].y << '\n';
}
void print ()
{
for ( int i = 0; i < n; ++i )
fout << fixed << setprecision (12) << v[i].x << " " << v[i].y << '\n';
fout << '\n';
}