Pagini recente » Cod sursa (job #1851225) | Cod sursa (job #1404534) | Cod sursa (job #1759148) | Cod sursa (job #2863357) | Cod sursa (job #1987219)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
int const nmax = 120000;
struct Point {
double x;
double y;
bool operator<(Point other) const {
if (x != other.x)
return (x < other.x);
else
return (y < other.y);
}
};
//|a.x a.y 1|
//|b.x b.y 1|
//|c.x c.y 1|
double det3(Point a, Point b, Point c) {
double plus = a.x * b.y + a.y * c.x + b.x * c.y;
double minus = c.x * b.y + b.x * a.y + a.x * c.y;
return (plus - minus);
}
int n, nst;
Point p[1 + nmax];
Point st[1 + nmax];
bool compare(Point a, Point b) {
return (det3(p[1], a, b) < 0);
}
void convexhull() {
nst = 2;
st[1] = p[1];
st[2] = p[2];
for (int i = 3; i <= n; i++) {
while (2 < nst && (det3(st[nst - 1], st[nst], p[i]) > 0))
nst--;
nst++;
st[nst] = p[i];
}
}
int main() {
in >> n;
int first = 1;
for (int i = 1; i <= n; i++) {
in >> p[i].x >> p[i].y;
if (p[i] < p[first])
first = i;
}
swap(p[1], p[first]);
sort(p + 1, p + n + 1, compare);
convexhull();
cout << nst << endl;
while (0 < nst) {
cout << setprecision(6) << fixed << st[nst].x << " " << st[nst].y << endl;
nst--;
}
return 0;
}