Pagini recente » Cod sursa (job #3159127) | Cod sursa (job #255653) | Cod sursa (job #2619821) | Cod sursa (job #2909293) | Cod sursa (job #2539650)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
#define NMAX 120000
#define inf 2000000000
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int n, m, vf;
pair <double, double> v[NMAX+10], ll=make_pair(inf, inf), stiva[NMAX+10];
inline bool mycmp(pair <double, double> a, pair <double, double> b)
{ return (a.second * b.first < a.first * b.second);
}
int area(pair <double, double> a, pair <double, double> b, pair <double, double> c)
{ double A = (a.first - b.first) * (a.second - c.second) - (a.second - b.second) * (a.first - c.first);
if(A < 0) return -1;
return 1;
}
int main()
{
f >> n;
for(int i=1; i<=n; i++)
{ f >> v[i].first >> v[i].second;
if(v[i].second < ll.second || (v[i].second == ll.second && v[i].first < ll.first)) ll = v[i];
}
for(int i=1; i<=n; i++)
{ v[i].first -= ll.first;
v[i].second -= ll.second;
if(v[i].first != 0 || v[i].second != 0) v[++m] = v[i];
}
n = m;
sort(v+1, v+n+1, mycmp);
v[n+1] = v[1];
stiva[++vf] = make_pair(0, 0);
stiva[++vf] = v[1];
stiva[++vf] = v[2];
for(int i=3; i<=n+1; i++)
{ while(vf > 2 && area(stiva[vf-2], stiva[vf-1], stiva[vf]) != area(stiva[vf-1], stiva[vf], v[i])) vf--;
stiva[++vf] = v[i];
}
g << vf-1 << '\n';
g << setprecision(6) << fixed;
for(int i=1; i<vf; i++) g << stiva[i].first + ll.first << ' ' << stiva[i].second + ll.second << '\n';
return 0;
}