Pagini recente » Cod sursa (job #2555841) | Cod sursa (job #190726) | Cod sursa (job #12526) | Cod sursa (job #24152) | Cod sursa (job #1515456)
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
#define x second
#define y first
using namespace std;
ifstream is("infasuratoare.in");
ofstream os("infasuratoare.out");
int n, m;
vector<pair<double, double>> p, a;
void Read();
void Sort();
void Write();
void ConvexHull();
inline double CrossProduct(const pair<double, double>& a, const pair<double, double>& b, const pair<double, double>& c)
{
return ( a.x - b.x ) * ( a.y - c.y ) - ( a.x - c.x ) * ( a.y - b.y );
}
inline bool Cmp(const pair<double, double>& a, const pair<double, double>& b)
{
return CrossProduct(p[1], a, b) > 0;
}
int main()
{
Read();
Sort();
ConvexHull();
Write();
is.close();
os.close();
return 0;
}
void ConvexHull()
{
a[1] = p[1];
a[2] = p[2];
m = 2;
for ( int i = 3; i <= n; ++i )
{
while ( m >= 2 && CrossProduct(a[m - 1], a[m], p[i]) < 0 )
--m;
a[++m] = p[i];
}
}
void Write()
{
os << m << "\n";
for ( int i = 1; i <= m; ++i )
os << fixed << setprecision(9) << a[i].x << " " << a[i].y << "\n";
}
void Sort()
{
for ( int i = 2; i <= n; ++i )
if ( p[1] > p[i] )
swap(p[1], p[i]);
sort(p.begin() + 2, p.begin() + n + 1, Cmp);
}
void Read()
{
is >> n;
a = p = vector<pair<double, double>>(n + 1);
for ( int i = 1; i <= n; ++i )
is >> p[i].x >> p[i].y;
}