Pagini recente » Cod sursa (job #657414) | Cod sursa (job #1656852) | Cod sursa (job #782950) | Cod sursa (job #1336730) | Cod sursa (job #2524044)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
const int MAX_N = 120003;
const double EPS = 1e-12;
int n;
pair<double, double>p[MAX_N];
vector<pair<double, double>>hull;
pair<double,double>center;
inline double cross(pair<double, double>a, pair<double, double>b, pair<double, double>c)
{
return (a.first - c.first) * (b.second - c.second) - (a.second - c.second) * (b.first - c.first);
}
inline bool cmp(const pair<double, double>&a, const pair<double, double>&b)
{
return cross(center, a, b) > EPS;
}
void gethull()
{
for (int i = 1; i <= n; ++i)
{
while (hull.size() >= 2 && cross(hull[hull.size() - 2], hull[hull.size() - 1], p[i]) > EPS)
hull.pop_back();
hull.push_back(p[i]);
}
}
void Printhull()
{
fout << hull.size() << '\n';
fout << fixed << setprecision(12);
reverse(begin(hull), end(hull));
for (auto i : hull)
fout << i.first << ' ' << i.second << '\n';
}
int main()
{
fin >> n;
for (int i = 1; i <= n; ++i)
{
fin >> p[i].first >> p[i].second;
center.first+=p[i].first;
center.second+=p[i].second;
}
sort(p + 1, p + n + 1, cmp);
gethull (), Printhull();
}