Pagini recente » Cod sursa (job #1924308) | Cod sursa (job #3122727) | Cod sursa (job #651778) | Cod sursa (job #3261241) | Cod sursa (job #1395287)
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
#define x first
#define y second
ifstream is("infasuratoare.in");
ofstream os("infasuratoare.out");
const int Nmax = 120002;
using Punct = pair<double, double>;
int n, top;
Punct p[Nmax];
Punct A[Nmax];
void Read();
inline double CrossProduct(const Punct& A, const Punct& B, const Punct& C);
inline int Cmp(const Punct& p1, const Punct& p2);
void Sortare();
void Infasuratoare();
void Write();
int main()
{
Read();
Infasuratoare();
Write();
is.close();
os.close();
return 0;
}
void Read()
{
is >> n;
for ( int i = 1; i <= n; ++i )
is >> p[i].x >> p[i].y;
}
inline double CrossProduct(const Punct& A, const Punct& B, const Punct& C)
{
return (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x);
}
inline int Cmp(const Punct& p1, const Punct& p2)
{
return CrossProduct(p[1], p1, p2) > 0;
}
void Sortare()
{
int pos = 1;
for ( int i = 1; i <= n; ++i )
if ( p[i] < p[pos] )
pos = i;
swap(p[1], p[pos]);
sort(p + 2, p + n + 1, Cmp);
}
void Infasuratoare()
{
Sortare();
A[1] = p[1];
A[2] = p[2];
top = 2;
for ( int i = 3; i <= n; ++i )
{
while ( top >= 2 && CrossProduct(A[top - 1], A[top], p[i]) < 0 )
--top;
A[++top] = p[i];
}
}
void Write()
{
os << top << '\n';
os << fixed;
for ( int i = 1; i <= top; ++i )
os << setprecision(6) << A[i].x << ' ' << A[i].y << '\n';
}