Pagini recente » Cod sursa (job #1200011) | Cod sursa (job #908545) | Cod sursa (job #1344075) | Cod sursa (job #1212641) | Cod sursa (job #2246034)
#include <cstdio>
#include <vector>
#include <cmath>
using namespace std;
double eps = pow(10, -12);
struct point
{
double x, y;
};
point points[120002];
double ab(double x)
{
if(x>0)
return x;
return 0-x;
}
double cross_product(const point &A, const point &B, const point &C)
{
return (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x);
}
int comp(const point &p1, const point &p2)
{
double cp = cross_product(points[1], p1, p2);
if (cp < 0)
return -1;
if (cp == 0)
return 0;
return 1;
}
bool eq(const double &x1, const double &x2)
{
return ab(x1-x2) < eps;
}
bool operator ==(const point &p1, const point &p2)
{
return eq(p1.x, p2.x) && eq(p1.y, p2.y);
}
void quicksort(int st, int dr)
{
if(st >= dr)
return;
int i, j;
point aux;
i = st-1;
for(j=st; j<dr; ++j)
if (comp(points[j], points[dr]) > 0)
{
++i;
aux = points[i];
points[i] = points[j];
points[j] = aux;
}
aux = points[dr];
points[dr] = points[i+1];
points[i+1] = aux;
/*
for(j=st; j<=dr; ++j)
{
if(j == i+1)
printf("pivot ");
printf("%f %f\n", points[j].x, points[j].y);
}
printf("\n");
*/
quicksort(st, i);
quicksort(i+2, dr);
}
int main()
{
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
int n, i, min_ind = 1;
point aux;
scanf("%d", &n);
for(i=1; i<=n; ++i)
{
scanf("%lf%lf", &points[i].x, &points[i].y);
if (points[i].y < points[min_ind].y)
min_ind = i;
if (eq(points[i].y, points[min_ind].y) && points[i].x < points[min_ind].x)
min_ind = i;
}
aux = points[min_ind];
points[min_ind] = points[1];
points[1] = aux;
quicksort(2, n);
points[n+1] = points[1];
/*
for(i=1; i<=n; ++i)
printf("%f %f\n", points[i].x, points[i].y);
printf("\n");
*/
point st[n+1];
st[1] = points[1];
st[2] = points[2];
min_ind = 2;
for(i=3; i<=n; ++i)
{
while(min_ind >=2 && cross_product(st[min_ind-1], st[min_ind], points[i]) < 0)
--min_ind;
st[++min_ind] = points[i];
}
printf("%d\n", min_ind);
for(i=1; i<=min_ind; ++i)
printf("%f %f\n", st[i].x, st[i].y);
return 0;
}