Pagini recente » Cod sursa (job #1318556) | Cod sursa (job #1112707) | Cod sursa (job #690742) | Cod sursa (job #1329105) | Cod sursa (job #2628261)
#include <cstdio>
#include <cmath>
#include <algorithm>
const double eps=1.0e-12;
struct POINT
{
double x, y;
};
POINT p[120005];
int ccw(POINT p1, POINT p2, POINT p3)
{
double cp;
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;
}
POINT ll;
bool cmp(POINT a, POINT b)
{
if(a.x == ll.x && a.y == ll.y)
return 1;
if(b.x == ll.x && b.y == ll.y)
return 0;
return (ccw(ll, a, b) > 0);
}
int s[120005];
int top = 0;
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
int n;
scanf("%d",&n);
scanf("%lf%lf",&p[1].x,&p[1].y);
ll = p[1];
for(int i = 2; i <= n; i++)
{
scanf("%lf%lf",&p[i].x,&p[i].y);
if(p[i].x == ll.x)
{
if(p[i].y < ll.y)
ll = p[i];
}
else if(p[i].x < ll.x)
{
ll = p[i];
}
}
std::sort(p+1, p+n+1, cmp);
for(int i = 1; i <= n; i++)
{
while(top >= 2 && ccw(p[s[top-1]], p[s[top]], p[i])<=0)
{
top--;
}
top++;
s[top]= i;
}
while(top >= 2 && ccw(p[s[top-1]], p[s[top]], p[0])<=0)
{
top--;
}
top++;
s[top]= 0;
top--;
printf("%d\n",top);
for(int i = 1; i <= top; i++)
{
printf("%f %f\n",p[s[i]].x,p[s[i]].y);
}
return 0;
}