Pagini recente » Cod sursa (job #2968930) | Cod sursa (job #158205) | Cod sursa (job #2670878) | Cod sursa (job #2764733) | Cod sursa (job #411962)
Cod sursa(job #411962)
// Catalin Balan
// Fri Mar 5 10:00:26 EET 2010
// Infoarena - Infasuratoare convexa
#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;
#define NMAX 120003
#define FIN "infasuratoare.in"
#define FOUT "infasuratoare.out"
double x[NMAX],y[NMAX];
int ind[NMAX], n, luate[NMAX];
// p1 - punctu nou, p2 - ultimul punct adaugat, p3 - penultimul punct adaugat
// semn < 0 - intoarcere spre stanga; semn > 0 spre dreapta
long double semn(int p1, int p2, int p3)
{
return (long double)(x[p1] - x[p3]) * (y[p2] - y[p3]) - (long double)(y[p1] - y[p3]) * (x[p2] - x[p3]);
}
bool cmp(int a, int b)
{
if (x[a] == x[ind[1]]) return false;
if (x[b] == x[ind[1]]) return true;
return ( (long double)(x[b] - x[ind[1]]) * (y[a] - y[ind[1]]) <
(long double)(x[a] - x[ind[1]]) * (y[b] - y[ind[1]]) );
}
int main(int argv, char ** argc)
{
freopen(FIN, "r", stdin);
freopen(FOUT, "w", stdout);
int p;
scanf("%d\n", &n);
double minx, miny;
minx = miny = 1000000003;
for (int i = 1; i <= n; ++i)
{
scanf("%lf %lf", &x[i], &y[i]);
ind[i] = i;
if ( x[i] < minx || (x[i] == minx && y[i] < miny))
{
miny = y[i];
minx = x[i];
p = i;
}
}
ind[p] = 1;
ind[1] = p;
sort (ind+2, ind+n+1, cmp);
// for (int i = 1; i <= n; ++i) fprintf(stderr, "%lf %lf\n", x[ind[i]], y[ind[i]]);
// fprintf(stderr, "\n\n");
luate[1] = ind[1];
luate[2] = ind[2];
p = 2;
for (int i = 3; i <= n; ++i)
{
// fprintf(stderr, "%d %d %llf\n", i, p, semn( ind[i], luate[p], luate[p-1] ) );
while ( semn( ind[i], luate[p], luate[p-1] )>0 )
{
--p;
// fprintf(stderr, "%d %d %llf\n", i, p, semn( ind[i], luate[p], luate[p-1] ) );
}
luate[++p] = ind[i];
}
printf("%d\n", p);
for (int i = 1; i <= p; ++i) printf("%lf %lf\n", x[luate[i]], y[luate[i]]);
return EXIT_SUCCESS;
}