Pagini recente » Cod sursa (job #1911423) | Cod sursa (job #1088340) | Cod sursa (job #291559) | Cod sursa (job #3212492) | Cod sursa (job #2721308)
#include <iostream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#define NMAX 120000
#define ld long double
#define f first
#define s second
#define inf 2000000000
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int n, m;
pair <ld, ld> v[NMAX+10];
pair <ld, ld> LL = {inf, inf}, stiva[NMAX+10];
bool mycmp(pair <ld, ld> a, pair <ld, ld> b)
{ return a.s * b.f < a.f * b.s;
}
int A(pair <ld, ld> a, pair <ld, ld> b, pair <ld, ld> c)
{ ld val = (a.f - b.f) * (a.s - c.s) - (a.s - b.s) * (a.f - c.f);
if(val < 0) return -1;
return 1;
}
int main()
{
fin >> n;
for(int i=1; i<=n; i++)
{ fin >> v[i].f >> v[i].s;
if(v[i].s < LL.s)
LL = v[i];
else if(v[i].s == LL.s && v[i].f < LL.f)
LL = v[i];
}
for(int i=1; i<=n; i++)
{ if(v[i] == LL)
continue;
v[++m] = {v[i].f - LL.f, v[i].s - LL.s};
}
n = m;
v[0] = {0, 0};
sort(v+1, v+n+1, mycmp);
stiva[1] = {0, 0};
stiva[2] = v[1];
stiva[3] = v[2];
int vf = 3;
for(int i=3; i<=n; i++)
{ while(vf >= 3 && A(stiva[vf-2], stiva[vf-1], stiva[vf]) != A(stiva[vf-1], stiva[vf], v[i]))
vf--;
stiva[++vf] = v[i];
}
fout << vf << '\n';
fout << setprecision(12) << fixed;
for(int i=1; i<=vf; i++)
fout << stiva[i].f + LL.f << ' ' << stiva[i].s + LL.s << '\n';
return 0;
}