Pagini recente » Cod sursa (job #213339) | Cod sursa (job #1083859) | Cod sursa (job #3181621) | Cod sursa (job #3172788) | Cod sursa (job #3208012)
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
#define NMAX 120005
struct punct {
double x, y;
} p[NMAX];
int st[NMAX];
double det(punct a, punct b, punct c) {
return a.x * b.y + b.x * c.y + c.x * a.y - c.x * b.y - a.x * c.y - b.x * a.y;
}
bool cmp(punct a, punct b) {
return det(p[1], a, b) > 0;
}
int main() {
int n;
fin >> n;
int minim = 1;
for (int i = 1; i <= n; ++i) {
fin >> p[i].x >> p[i].y;
if (p[i].x < p[minim].x
|| (p[i].x == p[minim].x && p[i].y < p[minim].y)) {
minim = i;
}
}
swap(p[1], p[minim]);
sort(p + 2, p + n + 1, cmp);
p[n + 1] = p[1];
st[1] = 1;
st[2] = 2;
int vf = 2;
for (int i = 3; i <= n; ++i) {
while (vf > 1 && det(p[st[vf - 1]], p[st[vf]], p[i]) < 0) {
vf--;
}
st[++vf] = i;
}
fout << vf << '\n';
for (int i = 1; i <= vf; ++i) {
fout << setprecision(6) << fixed << p[st[i]].x << ' ' << p[st[i]].y << '\n';
}
return 0;
}