Pagini recente » Borderou de evaluare (job #1251848) | Borderou de evaluare (job #3358750) | Borderou de evaluare (job #1251835) | Borderou de evaluare (job #1256640) | Cod sursa (job #3358024)
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct punct {
double x, y;
};
bool cmp(punct a, punct b) {
if (a.x == b.x)
return a.y < b.y;
return a.x < b.x;
}
long long det(punct a, punct b, punct c) {
double val = (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
if (val < 0) return -1;
if (val > 0) return 1;
return 0;
}
int main() {
int n;
fin >> n;
punct p[120005];
for (int i = 0; i < n; ++i) {
fin >> p[i].x >> p[i].y;
}
sort(p, p + n, cmp);
punct stiva[120005];
int vf = 0;
for (int i = 0; i < n; ++i) {
while (vf >= 2 && det(stiva[vf - 2], stiva[vf - 1], p[i]) <= 0)
vf--;
stiva[vf++] = p[i];
}
int jos = vf;
for (int i = n - 2; i >= 0; --i) {
while (vf > jos && det(stiva[vf - 2], stiva[vf - 1], p[i]) <= 0)
vf--;
stiva[vf++] = p[i];
}
vf--;
fout << fixed << setprecision(6);
fout << vf << "\n";
for (int i = 0; i < vf; ++i) {
fout << stiva[i].x << " " << stiva[i].y << "\n";
}
fin.close();
fout.close();
return 0;
}