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