Pagini recente » Cod sursa (job #2681355) | Cod sursa (job #2404620) | Autentificare | Cod sursa (job #3277357) | Cod sursa (job #3148692)
#include <bits/stdc++.h>
#define cin in
#define cout out
#define eb emplace_back
#define pii pair<double, double>
using namespace std;
const string file_name("infasuratoare");
ifstream in(file_name + ".in");
ofstream out(file_name + ".out");
struct date
{
double x, y;
} v[150];
int n, vf, pos;
int s[150];
double xmin, ymin = DBL_MAX, x, y;
int convex(date a, date b, date c)
{
double rez = a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y);
return rez > 0;
}
int main()
{
cout<<fixed<<setprecision(20);
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> v[i].x >> v[i].y;
if (ymin > v[i].y)
{
xmin = v[i].x;
ymin = v[i].y;
pos = i;
}
}
for (int i = 1; i <= n; i++)
v[i].x -= xmin,
v[i].y -= ymin;
swap(v[1], v[pos]);
sort(v + 2, v + n + 1, [](date a, date b)
{ return a.x * b.y >= b.x * a.y; });
s[1] = 1;
s[2] = 2;
vf = 2;
for (int i = 3; i <= n; i++)
{
while (vf >= 3 and !convex(v[s[vf - 1]], v[s[vf]], v[i]))
vf--;
s[++vf] = i;
}
cout << vf << '\n';
for (int i = 1; i <= vf; i++)
cout << v[s[i]].x + xmin << ' ' << v[s[i]].y + ymin << '\n';
return 0;
}