Pagini recente » Cod sursa (job #6204) | Cod sursa (job #1596373) | Cod sursa (job #45394) | Cod sursa (job #2881161) | Cod sursa (job #1226594)
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
const double eps=1.e-12;
struct point
{
double x, y;
};
point p[120005], ll;
int st[120005];
int ccw(point a, point b, point c)
{
double val=(b.x-a.x)*(c.y-b.y)-(b.y-a.y)*(c.x-b.x);
if(val>=eps)return 1;
if(val<=-eps)return -1;
return 0;
}
bool cmp(point a, point b)
{
return ccw(ll, a, b)>0;
}
int main()
{
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
int n;
double tx, ty;
scanf("%d%lf%lf", &n, &tx, &ty);
ll.x=tx;ll.y=ty;
for(int i=1;i<n;i++)
{
scanf("%lf%lf", &tx, &ty);
p[i].x=tx;p[i].y=ty;
if(ty-ll.y<=-eps || (fabs(ty-ll.y)<eps && tx-ll.x<=-eps))
{
double aux=ll.x;
ll.x=p[i].x;
p[i].x=aux;
aux=ll.y;
ll.y=p[i].y;
p[i].y=aux;
}
}
p[0]=ll;
sort(p+1, p+n, cmp);
p[n]=p[0];
st[0]=0;st[1]=1;
int top=1, i=2;
while(i<=n)
{
if(ccw(p[st[top-1]], p[st[top]], p[i])>0)
{
st[++top]=i;
i++;
}
else --top;
}
printf("%d\n", top);
for(int i=0;i<top;i++)
printf("%lf %lf\n", p[st[i]].x, p[st[i]].y);
return 0;
}