Pagini recente » Cod sursa (job #1465217) | Cod sursa (job #2402633) | Cod sursa (job #2377263) | Cod sursa (job #1507146) | Cod sursa (job #1465237)
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ofstream fout("infasuratoare.out");
ifstream fin("infasuratoare.in");
const int NMAX = 120005;
const double EPS = 1e-12;
int n, lg, H;
struct punct { double x, y; } p[NMAX];
punct sol[NMAX];
bool cmp(punct a, punct b) { return a.x < b.x; }
void citire()
{
fin >> n;
for(int i=1; i<=n; i++) fin >> p[i].x >> p[i].y;
}
void afis()
{
fout << lg << '\n';
for(int i=2; i<=lg+1; i++)
fout << setprecision(6) << fixed << sol[i].x << ' ' << sol[i].y << '\n';
}
double cross_product(punct det, punct a, punct b)
{
return (a.x - det.x) * (b.y - det.y) - (b.x - det.x) * (a.y - det.y);
}
void convex_hull()
{
sort(p + 1, p + n + 1, cmp);
for(int i=1; i<=n; i++) {
while(lg > 1 && cross_product(sol[lg-1], sol[lg], p[i]) < EPS)
lg--;
sol[++lg] = p[i];
}
for(int i=n, t=lg+1; i; i--) {
while(lg >= t && cross_product(sol[lg-1], sol[lg], p[i]) < EPS)
lg--;
sol[++lg] = p[i];
}
lg--;
}
int main()
{
citire();
convex_hull();
afis();
return 0;
}