Pagini recente » Cod sursa (job #1842115) | Cod sursa (job #328036) | Cod sursa (job #1921741) | Cod sursa (job #2317785) | Cod sursa (job #1071863)
#include<stdio.h>
#include<algorithm>
using namespace std;
#define NMAX 120010
#define INF 2000000000
struct punct
{
double x,y,tan;
};
punct v[NMAX];
int sol[NMAX],nr;
inline bool cmp(const punct &a,const punct &b)
{
return a.tan<b.tan;
}
inline bool det(const punct &a,const punct &b,const punct &c)
{
double s=(c.x-a.x)*(b.y-a.y)-(b.x-a.x)*(c.y-a.y);
if(s>=0)
return 1;
return 0;
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
int n,i,poz=1;
double xmin=INF,ymin;
scanf("%d",&n);
for(i=1;i<=n;++i)
{
scanf("%lf%lf",&v[i].x,&v[i].y);
if(v[i].x<xmin || (v[i].x==xmin&&v[i].y<ymin))
{
xmin=v[i].x;
ymin=v[i].y;
poz=i;
}
}
v[0]=v[1];
v[1]=v[poz];
v[poz]=v[0];
sol[++nr]=1;
for(i=1;i<=n;++i)
{
v[i].x-=xmin;
v[i].y-=ymin;
v[i].tan=v[i].y/v[i].x;
}
sort(v+2,v+1+n,cmp);
/////////
for(i=2;i<=n;++i)
{
sol[++nr]=i;
while(nr>2 && det(v[sol[nr-1]],v[sol[nr]],v[sol[nr-2]]))
{
sol[nr-1]=sol[nr];
sol[nr]=0;
--nr;
}
}
printf("%d\n",nr);
for(i=1;i<=nr;++i)
printf("%lf %lf\n",v[sol[i]].x+xmin,v[sol[i]].y+ymin);
return 0;
}