Pagini recente » Cod sursa (job #2018013) | Cod sursa (job #716487) | Cod sursa (job #3205645) | Cod sursa (job #2746769) | Cod sursa (job #1536767)
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("infasuratoare.in");
ofstream f2("infasuratoare.out");
#define NMAX 120120
struct Punct
{
double x, y;
};
bool operator<(Punct p1, Punct p2)
{
return p1.x < p2.x;
}
double delta(Punct p, Punct q, Punct r)
{
return (q.x - p.x) * (r.y - p.y) - (r.x - p.x)*(q.y - p.y);
}
int n, kSt;
Punct p[NMAX], st[NMAX];
int main()
{
int i;
f >> n;
for (i=1; i<=n; i++)
f >> p[i].x >> p[i].y;
// graham's scan (Andrew )
sort(p+1, p+n+1);
st[++kSt]= p[1];
st[++kSt]= p[2];
for (i=3; i<=n; i++)
{
while ( delta(st[kSt-1], st[kSt], p[i]) < 0 && kSt > 1 )
kSt--;
st[++kSt]= p[i];
}
st[++kSt]= p[n-1];
for (i=n-2; i>=1; i--)
{
while ( delta(st[kSt-1], st[kSt], p[i]) < 0 && kSt > 1 )
kSt--;
st[++kSt]= p[i];
}
kSt--;
// output
f2.precision(6);
f2.setf( ios::fixed, ios::floatfield );
f2 << kSt << "\n";
for (i=1; i<= kSt; i++)
f2 << st[i].x << " " << st[i].y << "\n";
f2.close();
return 0;
}