Pagini recente » Cod sursa (job #1472286) | Cod sursa (job #1622225) | Cod sursa (job #2594632) | Cod sursa (job #487827) | Cod sursa (job #2575335)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
#define inf 2000000000
#define NMAX 120000
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int n, p, vf;
pair <double, double> ll, v[NMAX+10], stiva[NMAX+10];
int area(pair <double, double> a, pair <double, double> b, pair <double, double> c)
{ double Area = (a.first - b.first) * (a.second - c.second) - (a.second - b.second) * (a.first - c.first);
if(Area < 0) return -1;
return 1;
}
inline bool mycmp(pair <double, double> a, pair <double, double> b)
{ return (a.second * b.first < a.first * b.second);
}
int main()
{
f >> n;
ll = make_pair(inf, inf);
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], p = i;
}
for(int i=1; i<=n; i++) v[i].first -= ll.first, v[i].second -= ll.second;
swap(v[1], v[p]);
sort(v+2, v+n+1, mycmp);
v[++n] = v[1];
for(int i=1; i<=3; i++) stiva[++vf] = v[i];
for(int i=4; i<=n; 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;
}