Pagini recente » Cod sursa (job #2265618) | Cod sursa (job #2493288) | Cod sursa (job #207158) | Cod sursa (job #1925124) | Cod sursa (job #2402053)
#include<cstdio>
#include<cmath>
#include<vector>
#include<algorithm>
using namespace std;
struct POINT
{
double x,y;
};
const double eps=1e-8;
POINT LL;
vector<POINT>v;
double cp(POINT P1, POINT P2, POINT P3)
{
return (P3.y-P2.y)*(P2.x-P1.x) - (P3.x-P2.x)*(P2.y-P1.y);
}
int ccw(POINT P1, POINT P2, POINT P3)
{
double cpp=cp(P1,P2,P3);
if(fabs(cpp)<eps) return 0;
if(cpp>eps) return 1;
return -1;
}
bool cmp(POINT P1, POINT P2)
{
int cccw=ccw(LL,P1,P2);
return cccw==1;
}
int h[120005];
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
int n;
scanf("%d",&n);
double x,x1,xL,yL;
POINT temp;
for(register int i=1;i<=n;i++)
{
scanf("%lf%lf",&x,&x1);
if(i==1)
{
xL=x;
yL=x1;
}
else
{
if(yL==x1&&x<xL) xL=x;
else if(x1<yL)
{
xL=x;
yL=x1;
}
}
temp.x=x;
temp.y=x1;
v.push_back(temp);
}
LL.x=xL;
LL.y=yL;
sort(v.begin(),v.end(),cmp);
// for(register int i=0;i<=v.size();i++)
// printf("%lf %lf\n",v[i].x,v[i].y);
h[1]=0;
h[2]=1;
int top=2,i=2;
while(i<=n-1)
{
if(ccw(v[h[top-1]],v[h[top]],v[i])>0)
{
h[++top]=i;
i++;
}
else top--;
}
// for(i=1;i<=top;i++)
// printf("%d \n",h[i]);
printf("%d\n",top);
for(i=1;i<=top;i++)
printf("%lf %lf\n",v[h[i]].x,v[h[i]].y);
return 0;
}