Pagini recente » Cod sursa (job #2112837) | Cod sursa (job #1470857) | Cod sursa (job #2850081) | Cod sursa (job #2094949) | Cod sursa (job #1468760)
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <deque>
#define INF ( (1 << 30) - 1 + (1 << 30) )
#define mod 666013
#define eps 1e-12
using namespace std;
struct punct
{
double x, y;
}v[120005];
int n, i, q, st[120005], ap[120005];
bool cmp(punct a, punct b)
{
if( fabs(a.x - b.x) < eps) return a.y < b.y;
return a.x < b.x;
}
double det(punct a, punct b, punct c)
{
return (double)( a.x * b.y + b.x * c.y + c.x * a.y - a.y * b.x - b.y * c.x - c.y * a.x );
}
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);
sort(v + 1, v + n + 1, cmp);
st[1] = 1;
st[2] = 2;
ap[2] = 1;
q = 2;
for(i = 3; i <= n; i++)
{
if(ap[i])
continue;
while(q >= 2 && det( v[ st[q - 1] ], v[ st[q] ], v[i] ) < eps)
{
ap[ st[q] ] = 0;
q--;
}
st[ ++q ] = i;
ap[i] = 1;
}
for(i = n; i > 0; i--)
{
if(ap[i])
continue;
while(q >= 2 && det( v[ st[q - 1] ], v[ st[q] ], v[i] ) < eps)
{
ap[ st[q] ] = 0;
q--;
}
st[ ++q ] = i;
ap[i] = 1;
}
q--;
printf("%d\n", q);
for(i = 1; i <= q; i++)
printf("%.6f %.6f\n", v[ st[i] ].x, v[ st[i] ].y);
return 0;
}