Pagini recente » Cod sursa (job #1916057) | Cod sursa (job #2951111) | Cod sursa (job #1716970) | Cod sursa (job #112480) | Cod sursa (job #999195)
Cod sursa(job #999195)
#include <cstdio>
#include <algorithm>
#include <stack>
#define x first
#define y second
using namespace std;
const int eps = 1e-12;
typedef pair <double, double> point;
int n, i, top, st[120005];
bool visited[120005];
point v[120005];
double cross_product(point prev, point curr, point next)
{
return (curr.x - prev.x) * (next.y - prev.y) - (next.x - prev.x) * (curr.y - prev.y);
}
inline void convex_hull()
{
sort(v+1, v+n+1);
st[++top] = 1;
for (int i = 2, p = 1; i > 0; i += (p = (i == n ? -p : p)))
if(!visited[i])
{
while( cross_product( v[ st[top-1] ], v[ st[top] ], v[i]) <= eps && top >= 2)
visited[ st[top--] ] = 0;
visited[ st[++top]=i ] = 1;
}
}
int main()
{
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
scanf("%d", &n);
for(i=1; i<=n; ++i)
scanf("%lf %lf", &v[i].x, &v[i].y);
convex_hull();
printf("%d\n", top-1);
for(i=1; i<top; ++i)
printf("%6lf %6lf\n", v[ st[i] ].x, v[ st[i] ].y);
return 0;
}