Pagini recente » Cod sursa (job #854794) | Cod sursa (job #173112) | Cod sursa (job #2585263) | Cod sursa (job #3031687) | Cod sursa (job #2669276)
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
#define x first
#define y second
using namespace std;
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
const int NMAX = 120000;
int N;
pair < long double, long double > v[NMAX + 5];
bool ccw(pair<long double, long double> A, pair<long double, long double> B, pair<long double, long double> C) {
return (B.y - A.y) * (C.x - A.x) < (C.y - A.y) * (B.x - A.x);
}
inline bool cmp(const pair<long double, long double> A, const pair<long double, long double> B) {
return ccw(v[1], A, B);
}
int main()
{
cin >> N;
for(int i = 1; i <= N; i++)
cin >> v[i].x >> v[i].y;
for(int i = 2; i <= N; i++)
if(v[1] > v[i]) swap(v[1], v[i]);
sort(v + 2, v + N + 1, cmp);
vector < pair<long double, long double> > hull;
hull.push_back(v[1]);
for(int i = 2; i <= N; i++) {
while(hull.size() > 1 && !ccw(hull[(int)hull.size() - 2], hull[(int)hull.size() - 1], v[i]))
hull.pop_back();
hull.push_back(v[i]);
}
cout << (int)hull.size() << '\n';
for(auto it : hull) {
cout << fixed << setprecision(12) << it.x << ' ' << it.y << '\n';
}
return 0;
}