Pagini recente » Cod sursa (job #298464) | Cod sursa (job #2747376) | Cod sursa (job #636374) | Cod sursa (job #2869666) | Cod sursa (job #2907090)
#include <bits/stdc++.h>
#include <algorithm>
#include <iomanip>
#define x first
#define y second
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
typedef pair<double, double> STR;
long double eroare = 1e-12;
STR v[120002];
STR ans[120002];
STR res[120002];
int c, i, n, vf, ok[120002], st[120002];
long double maxim;
long double prod(STR K, STR L, STR M)
{
return (L.x - K.x) * (M.y - K.y) - (M.x - K.x) * (L.y - K.y);
}
int main()
{
fin >> n;
for(i = 1; i <= n; i++)
{
fin >> v[i].first >> v[i].second;
if(v[i].second > maxim) maxim = v[i].second;
}
sort(v + 1, v + n + 1);
c = 1;
vf = 2;
st[1] = 1;
st[2] = 2;
ok[2] = 1;
int p = 1;
for(i = 1; i > 0; i += p)
{
if(ok[i]) continue;
while(vf > 1 && prod(v[st[vf - 1]], v[st[vf]], v[i]) < eroare)
ok[st[vf--]] = 0;
st[++vf] = i;
ok[i] = 1;
if(i == n) p = -1;
}
// for(i = 1; i <= vf; i++) cout << v[st[i]].x << ' ' << v[st[i]].y << '\n';
fout << vf - 1 << '\n';
for(i = 1; i < vf; i++) ans[i].x = v[st[i]].x, ans[i].y = v[st[i]].y;
for(i = 1; i < vf; i++) fout << fixed << setprecision(6) << ans[i].x << ' ' << ans[i].y << '\n';
}