Pagini recente » Cod sursa (job #3037893) | Cod sursa (job #2885996) | Cod sursa (job #2033426) | Cod sursa (job #2983259) | Cod sursa (job #1301068)
#include <iostream>
#include <fstream>
#include <cmath>
#include <iomanip>
#include <algorithm>
using namespace std;
struct Point {
double x, y;
};
#define nmax 120005
#define E 1e-12
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int n;
Point A[nmax];
int i, len;
int st[nmax];
bool viz[nmax];
bool cmp(Point a, Point b) {
if (a.y == b.y)
return a.x < b.x;
return a.y < b.y;
}
double det(Point O, Point A, Point B) {
return (A.x - O.x)*(B.y - O.y)-(A.y - O.y)*(B.x - O.x);
}
void read() {
fin >> n;
for (i=1; i<=n; i++)
fin >> A[i].x >> A[i].y;
}
void convex_hull() {
sort(A+1, A+n+1, cmp);
st[1] = 1, st[2] = 2, len = 2;
viz[1] = viz[2] = true;
for (i = 1; i <= n; i++) {
while (len > 1 && det(A[st[len-1]], A[st[len]], A[i]) < E)
viz[st[len--]] = false;
st[++len] = i;
viz[i] = true;
}
for (i = n-1; i > 0; i--) {
if (viz[i])
continue;
while (len > 1 && det(A[st[len-1]], A[st[len]], A[i]) < E)
len--;
st[++len] = i;
}
fout << len-1 << "\n";
fout << fixed;
for (i = 1; i < len; i++)
fout << setprecision(6) << A[st[i]].x << " " << A[st[i]].y << "\n";
}
int main() {
read();
convex_hull();
return 0;
}