Pagini recente » Cod sursa (job #1560203) | Cod sursa (job #3288806) | Cod sursa (job #1415113) | Cod sursa (job #2186793) | Cod sursa (job #2827593)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
const int MAX = 120001;
struct point {
long double x, y;
}a[MAX];
int n, st[MAX], p;
inline long double cross_product(point a, point b, point c) {
return -(a.x * b.y + c.x * a.y + b.x * c.y - c.x * b.y - a.x * c.y - b.x * a.y);
}
bool comp(point A, point B) {
return cross_product(a[1], A, B) > 0;
}
int main(){
in >> n;
int firstPoint = 1;
for (int i = 1; i <= n; i++) {
in >> a[i].x >> a[i].y;
if (a[firstPoint].y > a[i].y || (a[firstPoint].y == a[i].y && a[firstPoint].x > a[i].x))
firstPoint = i;
}
point aux = a[1];
a[1] = a[firstPoint];
a[firstPoint] = aux;
sort(a + 2, a + n + 1, comp);
/*
for (int i = 1; i <= n; i++)
cout << a[i].x << ' ' << a[i].y << '\n';
*/
st[++p] = 1;
st[++p] = 2;
for (int i = 3; i <= n; i++) {
while (p >= 2 && cross_product(a[st[p - 1]], a[st[p]], a[i]) < 0)
p--;
st[++p] = i;
}
out << p << '\n';
out << fixed << setprecision(12);
out << a[st[1]].x << ' ' << a[st[1]].y << '\n';
for (int i = p; i >= 2; i--)
out << a[st[i]].x << ' ' << a[st[i]].y << '\n';
return 0;
}