Pagini recente » Cod sursa (job #2342829) | Cod sursa (job #2807278) | Istoria paginii runda/arnold-testare/clasament | Istoria paginii runda/oji200911 | Cod sursa (job #1370376)
#include <fstream>
#include <algorithm>
#include <iomanip>
#define x second
#define y first
using namespace std;
ifstream is("infasuratoare.in");
ofstream os("infasuratoare.out");
typedef pair<double, double> Punct;
Punct P[100];
Punct V[100];
int n, top = 1;
void Read();
void Sortare();
void Write();
inline double CrossProduct(const Punct& A, const Punct& B, const Punct& C );
inline bool Cmp(const Punct& P1, const Punct& P2);
void Invelitoare();
int main()
{
Read();
Sortare();
Invelitoare();
Write();
is.close();
os.close();
return 0;
}
void Read()
{
is >> n;
for ( int i = 0; 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) - (C.x-A.x)*(B.y-A.y);
}
void Sortare()
{
int poz = 0;
for ( int i = 1; i < n; ++i )
if ( P[i] < P[poz] )
poz = i;
swap(P[0], P[poz]);
sort(P+1, P+n, Cmp );
}
inline bool Cmp(const Punct& P1, const Punct& P2)
{
return CrossProduct(P[0], P1, P2) > 0;
}
void Write()
{
//for ( int i = 0; i < n; ++i )
// os << P[i].x << ' ' << P[i].y << '\n';
os << top+1 << '\n';
for ( int i = 0; i <= top; ++i )
os << fixed << setprecision(6) << V[i].x << ' ' << V[i].y << '\n';
}
void Invelitoare()
{
V[0] = P[0];
V[1] = P[1];
for ( int i = 2; i < n; ++i )
{
while ( top >= 1 && CrossProduct(V[top-1], V[top], P[i]) < 0 )
top--;
V[++top] = P[i];
}
}