Pagini recente » Borderou de evaluare (job #3309663) | Diferente pentru template/algoritmiada-2012/header intre reviziile 1 si 2 | Atasamentele paginii Profil nverde1119 | Borderou de evaluare (job #3309659) | Cod sursa (job #3349072)
#include <algorithm>
#include <iomanip>
#include <fstream>
#include <vector>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
struct point {
double x, y;
};
const int nmax = 120005;
point v[nmax];
int det(point a, point b, point c)
{
int d1 = (b.x - a.x) * (c.y - a.y);
int d2 = (c.x - a.x) * (b.y - a.y);
if (d1 == d2) return 0;
return (d1 > d2 ? 1 : -1);
}
bool cmp(point a, point b) {
return a.y < b.y;
}
int main()
{
int n; f >> n;
for (int i = 1; i <= n; i++)
f >> v[i].x >> v[i].y;
sort(v + 1, v + n + 1, cmp);
vector<point> ans; ans.clear();
for (int i = 1; i <= n; i++)
{
while (ans.size() > 1 && det(ans[ans.size() - 2], ans.back(), v[i]) < 0) ans.pop_back();
ans.push_back(v[i]);
}
for (int i = n - 1; i > 1; i--)
{
while (ans.size() > 1 && det(ans[ans.size() - 2], ans.back(), v[i]) < 0) ans.pop_back();
ans.push_back(v[i]);
}
g << ans.size() << '\n';
for (auto a : ans) g << setprecision(12) << fixed << a.x << " " << a.y << '\n';
return 0;
}