Pagini recente » Cod sursa (job #3364916) | Cod sursa (job #3364924) | Cod sursa (job #3364925) | Cod sursa (job #3364927) | Cod sursa (job #3364887)
#include <fstream>
#include <iomanip>
#include <vector>
#include <algorithm>
using namespace std;
#define MAX 120005
ifstream cin ("infasuratoare.in");
ofstream cout ("infasuratoare.out");
struct Punct
{
double x, y;
};
int n;
double x, y;
vector <Punct> v;
int minn;
vector <Punct> rez;
double arie(const Punct& a, const Punct& b, const Punct& c)
{
return 0.5*(a.x*(b.y - c.y) + b.x*(c.y - a.y) + c.x*(a.y - b.y));
}
bool cmp(const Punct& a, const Punct& b)
{
return arie(v[0], a, b) >= 0;
}
Punct a, b, c;
int main()
{
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> x >> y;
v.push_back({x, y});
if (v[i].y < v[minn].y) minn = i;
}
swap(v[0], v[minn]);
sort(v.begin() + 1, v.end(), cmp);
rez.push_back(v[0]);
rez.push_back(v[1]);
for (int i = 2; i < n; i++)
{
while (arie(rez[rez.size() - 2], rez[rez.size() - 1], v[i]) < 0)
rez.pop_back();
rez.push_back(v[i]);
}
cout << rez.size() << '\n';
for (int i = 0 ; i < rez.size(); i++)
{
cout << fixed << setprecision(6) << rez[i].x << " ";
cout << fixed << setprecision(6) << rez[i].y << "\n";
}
return 0;
}