Pagini recente » Cod sursa (job #969722) | Cod sursa (job #387434) | Cod sursa (job #3201559) | Cod sursa (job #2434881) | Cod sursa (job #2517198)
#include <bits/stdc++.h>
using namespace std;
double det(pair <double, double> a, pair <double, double> b, pair <double, double> c)
{
return (a.first * b.second + b.first * c.second + c.first * a.second) - (b.second * c.first + c.second * a.first + a.second * b.first);
}
vector < pair <double, double> > ConvexHull(vector < pair <double, double> > v)
{
vector < pair <double, double> > stk;
stk.push_back(v[0]);
for (int i = 1;i < v.size();++i)
{
while (stk.size() >= 2 && det(stk[stk.size() - 2], stk.back(), v[i]) < 0)
stk.pop_back();
stk.push_back(v[i]);
}
return stk;
}
int main()
{
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int N;
fin >> N;
vector < pair <double, double> > points(N);
for (auto &p : points)
fin >> p.first >> p.second;
sort(points.begin(), points.end());
vector < pair <double, double> > under, over;
under.push_back(points[0]);
over.push_back(points[0]);
for (int i = 1;i < points.size() - 1;++i)
if (det(points[0], points[i], points.back()) >= 0)
under.push_back(points[i]);
else
over.push_back(points[i]);
under.push_back(points.back());
over.push_back(points.back());
reverse(over.begin(), over.end());
auto hullunder = ConvexHull(under);
auto hullover = ConvexHull(over);
hullunder.pop_back();
hullover.pop_back();
vector < pair <double, double> > hull;
for (auto &i : hullunder)
hull.push_back(i);
for (auto &i : hullover)
hull.push_back(i);
fout << hull.size() << "\n";
fout << setprecision(12) << fixed;
for (auto &i : hull)
fout << i.first << " " << i.second << "\n";
fin.close();
fout.close();
return 0;
}