Pagini recente » Cod sursa (job #59405) | Cod sursa (job #2265823) | Cod sursa (job #619467) | Cod sursa (job #1085630) | Cod sursa (job #916719)
Cod sursa(job #916719)
#include <cstdio>
#include <cmath>
#include <algorithm>
#define eps 1e-12
using namespace std;
struct punct
{
double x,y;
};
punct LL,p[120002];
int infasuratoare[120002];
double ccw(punct a,punct b,punct c)
{
return(b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}
bool cmp(punct a,punct b)
{
if(ccw(LL,a,b)>0)
return true;
return false;
}
int main()
{
punct aux;
int n,i,top;
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d",&n);
scanf("%lf%lf",&p[1].x,&p[1].y);
LL.x=p[1].x;
LL.y=p[1].y;
int pozll=1;
for(i=2;i<=n;i++)
{
scanf("%lf%lf",&p[i].x,&p[i].y);
if((p[i].y<LL.y)||(fabs(p[i].y-LL.y)<eps&&p[i].x<LL.x))
{
LL.x=p[i].x;
LL.y=p[i].y;
pozll=i;
}
}
aux.x=p[1].x;
aux.y=p[1].y;
p[1].x=p[pozll].x;
p[1].y=p[pozll].y;
p[pozll].x=aux.x;
p[pozll].y=aux.y;
sort(p+2,p+n+1,cmp);
p[n+1].x=LL.x;
p[n+1].y=LL.y;
i=3;
top=2;
infasuratoare[1]=1;
infasuratoare[2]=2;
while(i<=n)
{
if(ccw(p[infasuratoare[top-1]],p[infasuratoare[top]],p[i])>0)
{
top++;
infasuratoare[top]=i;
i++;
}
else
{
top--;
}
}
printf("%d\n",top);
for(i=1;i<=top;i++)
printf("%.6lf %.6lf\n",p[infasuratoare[i]].x,p[infasuratoare[i]].y);
return 0;
}