Pagini recente » Cod sursa (job #352327) | Cod sursa (job #1292755) | Cod sursa (job #3265671) | Cod sursa (job #1953421) | Cod sursa (job #2402104)
#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,y,xL,yL;
POINT temp;
scanf("%lf%lf",&xL,&yL);
temp.x=xL;
temp.y=yL;
v.push_back(temp);
for(register int i=2;i<=n;i++)
{
scanf("%lf%lf",&x,&y);
temp.x=x;
temp.y=y;
v.push_back(temp);
if((fabs(v[0].y-y)<eps&&(x-v[0].x)<(-eps))||(y-v[0].y<(-eps))) swap(v[0],v[i-1]);
}
LL.x=v[0].x;
LL.y=v[0].y;
sort(v.begin()+1,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)
{
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("%d ",h[i]);
printf("\n");
for(i=1;i<=top;i++)
printf("%lf %lf\n",v[h[i]].x,v[h[i]].y);
return 0;
}