Pagini recente » Cod sursa (job #2229358) | Cod sursa (job #2628387) | Cod sursa (job #1918191) | Cod sursa (job #643613) | Cod sursa (job #3215447)
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <vector>
#define MAX 120000
using namespace std;
ifstream cin ("infasuratoare.in");
ofstream cout ("infasuratoare.out");
struct ura
{
double x, y;
};
ura v[MAX + 10];
vector <ura> up, down;
bool cmp(const ura &a, const ura &b)
{
if (a.x < b.x)
return true;
if (a.x > b.x)
return false;
if (a.y < b.y)
return true;
return false;
}
double area(ura a, ura b, ura c)
{
return (a.x * b.y + b.x * c.y + c.x * a.y - c.x * b.y - a.x * c.y - b.x * a.y);
}
int main()
{
int n;
cin >> n;
for (int i = 1; i <= n; i++)
cin >> v[i].x >> v[i].y;
sort(v + 1, v + n + 1, cmp);
up.push_back(v[1]);
down.push_back(v[1]);
for (int i = 2; i <= n; i++)
{
while (up.size() >= 2 && area(up[up.size() - 1], up[up.size() - 2], v[i]) >= 0)
up.pop_back();
up.push_back(v[i]);
while (down.size() >= 2 && area(down[down.size() - 1], down[down.size() - 2], v[i]) <= 0)
down.pop_back();
down.push_back(v[i]);
}
cout << up.size() + down.size() - 2 << '\n';
cout << fixed << setprecision(12);
for (int i = 0; i < up.size(); i++)
cout << up[i].x << ' ' << up[i].y << '\n';
for (int i = down.size() - 1; i >= 1; i--)
cout << down[i].x << ' ' << down[i].y << '\n';
return 0;
}