Pagini recente » Cod sursa (job #2637462) | Cod sursa (job #3037507) | Cod sursa (job #2626830) | Cod sursa (job #2779346) | Cod sursa (job #2517200)
#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);
}
bitset <120005> seen;
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 <int> stk;
stk.push_back(0);
for (int i = 1;i < points.size();++i)
{
while (stk.size() >= 2 && det(points[stk[stk.size() - 2]], points[stk.back()], points[i]) < 0)
{
seen[stk.back()] = false;
stk.pop_back();
}
stk.push_back(i);
seen[i] = true;
}
for (int i = points.size() - 1;i >= 0;--i)
{
if (seen[i] == 1)
continue;
while (stk.size() >= 2 && det(points[stk[stk.size() - 2]], points[stk.back()], points[i]) < 0)
{
seen[stk.back()] = false;
stk.pop_back();
}
stk.push_back(i);
seen[i] = true;
}
stk.pop_back();
fout << stk.size() << "\n";
fout << setprecision(12) << fixed;
for (auto &i : stk)
fout << points[i].first << " " << points[i].second << "\n";
fin.close();
fout.close();
return 0;
}