Pagini recente » Cod sursa (job #1726636) | Cod sursa (job #1486193) | Cod sursa (job #2126377) | Cod sursa (job #936519) | Cod sursa (job #1364177)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <iomanip>
#define nmax 120005
#define E 0.000000000001
using namespace std;
struct point {
double x, y;
}P[nmax];
int n, nrPoints;
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 a, point b, point o) {
return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x);
}
int main() {
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
fin >> n;
for (int i = 1; i <= n; i++)
fin >> P[i].x >> P[i].y;
sort(P+1, P+n+1, cmp);
st[1] = 1;
st[2] = 2;
viz[1] = viz[2] = true;
nrPoints = 2;
for (int i = 2; i <= n; i++) {
while (nrPoints > 1 && det(P[st[nrPoints-1]], P[st[nrPoints]], P[i]) < E)
viz[st[nrPoints--]] = false;
st[++nrPoints] = i;
viz[i] = true;
}
for (int i = n; i > 0; i--) {
if (viz[i])
continue;
while (nrPoints > 1 && det(P[st[nrPoints-1]], P[st[nrPoints]], P[i]) < E)
nrPoints--;
st[++nrPoints] = i;
}
fout << nrPoints << "\n";
fout << fixed;
for (int i = 1; i <= nrPoints; i++)
fout << setprecision(6) << P[st[i]].x << " " << P[st[i]].y << "\n";
fin.close();
fout.close();
return 0;
}