Pagini recente » Cod sursa (job #2126606) | Cod sursa (job #2736518) | Cod sursa (job #2148615) | Cod sursa (job #2118367) | Cod sursa (job #2089459)
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <climits>
using namespace std;
struct point
{
double x,y;
};
const double eps = 1.e-14;
point ll;
int ccw(const point &p1,const point &p2,const point &p3)
{
double cp = (p2.x - p1.x) * (p3.y - p2.y) - (p2.y - p1.y) * (p3.x - p2.x);
if(fabs(cp) < eps)
return 0;
if(cp >= eps)
return 1;
return -1;
}
double dist(const point &a,const point &b)
{
return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
class cmp
{
public:
bool operator () (const point &p1,const point &p2)
{
int cp;
double d1,d2;
cp = ccw(ll,p1,p2);
if(cp == 0)
{
d1 = dist(ll,p1);
d2 = dist(ll,p2);
if(d1 - d2 <= -eps)
return 1;
else
return 0;
}
if(cp == -1)
return 0;
return 1;
}
};
point p[120005];
int h[120005];
int n;
int main()
{
freopen("infasuratoare.in", "r",stdin);
freopen("infasuratoare.out", "w",stdout);
int i,u,cp,poz;
scanf("%d", &n);
ll.x = ll.y = INT_MAX;
for(i = 0;i < n;i++)
{
scanf("%lf%lf", &p[i].x, &p[i].y);
if(p[i].y - ll.y <= -eps || (fabs(p[i].y - ll.y) < eps && p[i].x - ll.x <= -eps))
{
ll = p[i];
poz = i;
}
}
swap(p[0],p[poz]);
sort(p + 1,p + n,cmp());
p[n] = p[0];
h[1] = 0;
h[2] = 1;
i = 2;
u = 2;
while(i <= n)
{
cp = ccw(p[h[u - 1]],p[h[u]],p[i]);
if(cp > 0)
{
h[++u] = i;
++i;
}
else
u--;
}
u--;
printf("%d\n",u);
for(i = 1;i <= u;i++)
printf("%.6lf %.6lf\n",p[h[i]].x,p[h[i]].y);
return 0;
}