Pagini recente » Cod sursa (job #1874031) | Cod sursa (job #310810) | Cod sursa (job #2939452) | Cod sursa (job #1739580) | Cod sursa (job #1969402)
#include <bits/stdc++.h>
using namespace std;
const double eps = 1e-12;
const int Nmax = 120005;
bool egale(double a, double b)
{
a -= b;
return a < eps && a > -eps;
}
struct Point
{
double x, y;
bool operator < (const Point &other) const
{
if(egale(x, other.x)) return y < other.y;
return x < other.x;
}
} a[Nmax];
int n, i, st[Nmax];
bool used[Nmax];
bool wrong(Point a, Point b, Point c)
{
double arie;
arie = a.x * (b.y-c.y) + b.x * (c.y-a.y) + c.x * (a.y-b.y);
return arie < eps;
}
void solve()
{
int nr, i, add;
memset(used, 0, sizeof(used));
st[1] = 1; st[2] = 2; used[2] = 1; nr = 2;
for(i=3, add=1; !used[1]; i += add)
{
if(i == n) add = -1;
if(used[i]) continue;
while(nr>=2 && wrong(a[st[nr-1]], a[st[nr]], a[i])) used[st[nr--]] = 0;
st[++nr] = i;
used[i] = 1;
}
printf("%d\n", nr-1);
for(i=1; i<nr; ++i) printf("%.6lf %.6lf\n", a[st[i]].x, a[st[i]].y);
}
int main()
{
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
scanf("%d", &n);
for(i=1; i<=n; ++i) scanf("%lf %lf", &a[i].x, &a[i].y);
sort(a+1, a+n+1);
solve();
return 0;
}