Pagini recente » Cod sursa (job #1726164) | Cod sursa (job #1353513) | Cod sursa (job #1550743) | Cod sursa (job #1721144) | Cod sursa (job #2722751)
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
struct point
{
double x, y;
point()
{
x = 0;
y = 0;
}
point(double X, double Y)
{
x = X;
y = Y;
}
bool operator < (const point &that) const
{
if (x < that.x)
return true;
if (x == that.x && y < that.y)
return true;
return false;
}
bool operator > (const point &that) const
{
return !(*this < that);
}
};
int n;
int st[120001];
point v[120001];
double cross_product(const point &a, const point &b, const point &c)
{
return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}
bool cmp(const point &a, const point &b)
{
return (cross_product(v[1], a, b) < 0);
}
int main()
{
f >> n;
for (int i = 1; i <= n; i++)
f >> v[i].x >> v[i].y;
int first = 1;
for (int i=2; i<=n; i++)
if (v[i] < v[first])
first = i;
swap(v[1], v[first]);
sort(v + 2, v + n + 1, cmp);
int m = 2;
st[1] = 1;
st[2] = 2;
for (int i=3; i<=n; i++)
{
while (m >= 2 && cross_product(v[st[m-1]], v[st[m]], v[i]) > 0)
m--;
m++;
st[m] = i;
}
g << m << "\n";
for (int i=m; i>=1; i--)
g << fixed << setprecision(6) << v[st[i]].x << " " << v[st[i]].y << "\n";
return 0;
}