Pagini recente » Cod sursa (job #2538375) | Cod sursa (job #153867) | Cod sursa (job #2299100) | Cod sursa (job #328134) | Cod sursa (job #3040577)
#include <fstream>
#include <algorithm>
#include <vector>
#include <iomanip>
using namespace std;
ifstream in ("infasuratoare.in");
ofstream out ("infasuratoare.out");
const int max_size = 12e4 + 1;
pair <double, double> v[max_size];
vector <pair <double, double>> sus, jos, ans;
double orientare (pair <double, double> x, pair <double, double> y, pair <double, double> z)
{
return x.first * (y.second - z.second) + y.first * (z.second - x.second) + z.first * (x.second - y.second);
}
int main ()
{
int n;
in >> n;
for (int i = 1; i <= n; i++)
{
in >> v[i].first >> v[i].second;
}
sort(v + 1, v + n + 1);
sus.push_back(v[1]);
jos.push_back(v[1]);
for (int i = 2; i <= n; i++)
{
while (sus.size() > 1 && orientare(sus[sus.size() - 2], sus[sus.size() - 1], v[i]) >= 0)
{
sus.pop_back();
}
while (jos.size() > 1 && orientare(jos[jos.size() - 2], jos[jos.size() - 1], v[i]) <= 0)
{
jos.pop_back();
}
sus.push_back(v[i]);
jos.push_back(v[i]);
}
sus.pop_back();
reverse(sus.begin(), sus.end());
sus.pop_back();
for (auto f : jos)
{
ans.push_back(f);
}
for (auto f : sus)
{
ans.push_back(f);
}
out << ans.size() << '\n';
out << fixed << setprecision(6);
for (auto f : ans)
{
out << f.first << " " << f.second << '\n';
}
in.close();
out.close();
return 0;
}