Pagini recente » Cod sursa (job #2262974) | Cod sursa (job #395892) | Cod sursa (job #2259300) | Cod sursa (job #542252) | Cod sursa (job #2866162)
#include <fstream>
#include <iomanip>
#include <algorithm>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
struct point
{
double x, y;
bool operator < (const point &that) const
{
if (x < that.x)
return true;
if (x == that.x && y < that.y)
return true;
return false;
}
};
int n, m;
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;
for (int i = 2; i <= n; i++)
if (v[i] < v[1])
swap(v[i], v[1]);
sort(v + 2, v + n + 1, cmp);
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;
}