Pagini recente » Cod sursa (job #2614787) | Cod sursa (job #3141160) | Cod sursa (job #3210608) | Cod sursa (job #195093) | Cod sursa (job #3215454)
#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() - 2], up[up.size() - 1], v[i]) >= 0)
up.pop_back();
up.push_back(v[i]);
while (down.size() >= 2 && area(down[down.size() - 2], down[down.size() - 1], v[i]) <= 0)
down.pop_back();
down.push_back(v[i]);
}
up.pop_back();
reverse(up.begin(), up.end());
up.pop_back();
cout << up.size() + down.size() << '\n';
cout << fixed << setprecision(12);
for (const auto &it : down)
cout << it.x << ' ' << it.y << '\n';
for (const auto &it : up)
cout << it.x << ' ' << it.y << '\n';
return 0;
}