Pagini recente » Cod sursa (job #2135850) | Cod sursa (job #2137359) | Monitorul de evaluare | Cod sursa (job #3160844) | Cod sursa (job #3200090)
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream in ("infasuratoare.in");
ofstream out ("infasuratoare.out");
const int max_size = 12e4 + 1;
pair <double, double> pct[max_size];
vector <pair <double, double>> sus, jos, ans;
double arie (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 >> pct[i].first >> pct[i].second;
}
sort(pct + 1, pct + n + 1);
sus.push_back(pct[1]);
jos.push_back(pct[1]);
for (int i = 2; i <= n; i++)
{
while (sus.size() > 1 && arie(sus[sus.size() - 2], sus[sus.size() - 1], pct[i]) >= 0)
{
sus.pop_back();
}
while (jos.size() > 1 && arie(jos[jos.size() - 2], jos[jos.size() - 1], pct[i]) <= 0)
{
jos.pop_back();
}
sus.push_back(pct[i]);
jos.push_back(pct[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;
}