Pagini recente » Cod sursa (job #2588734) | Cod sursa (job #1440193) | Borderou de evaluare (job #1314095) | Cod sursa (job #287492) | Cod sursa (job #1967399)
#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;
inline long long 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(p[1], a, b) < EPS;
}
void gethull()
{
for (int i = 1; i <= n; ++i)
{
while (!hull.empty() and 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;
if (p[i] < p[1])
swap(p[1], p[i]);
}
sort(p + 2, p + n + 1, cmp);
gethull (), Printhull();
}