Pagini recente » Cod sursa (job #318329) | Cod sursa (job #2282336) | Cod sursa (job #3252488) | Cod sursa (job #588066) | Cod sursa (job #379872)
Cod sursa(job #379872)
#include<stdio.h>
#include<algorithm>
int mini;
using namespace std;
#define nmax 120002
struct point
{double x,y;};
int n,st[nmax],o[nmax];
point v[nmax];
bool cmp(int i, int j)
{
return ((v[i].y-v[mini].y)*(v[j].x-v[mini].x))<((v[j].y-v[mini].y)*(v[i].x-v[mini].x));
}
int semn(point p1, point p2, point p3)
{
double s;
s=(p2.x-p1.x)*(p3.y-p2.y)-(p2.y-p1.y)*(p3.x-p2.x);
if(s<0)
return -1;
if(s>0)
return 1;
return 0;
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d",&n);
int i;
v[mini].x=v[mini].y=1000000000;
for(i=1;i<=n;i++)
{
scanf("%lf%lf",&v[i].x,&v[i].y);
if(v[i].x<v[mini].x || (v[i].x==v[mini].x && v[i].y<v[mini].y))
mini=i;
}
for(i=1;i<mini;i++)
o[i]=i;
for(i=mini+1;i<=n;i++)
o[i-1]=i;
sort(o+1,o+n,cmp);
st[++st[0]]=mini;
for(i=1;i<n;i++)
{
while(st[0]>=3 && semn(v[st[st[0]-1]],v[st[st[0]]],v[o[i]])==-1)
st[0]--;
st[++st[0]]=o[i];
}
printf("%d\n",st[0]);
for(i=1;i<=st[0];i++)
printf("%lf %lf\n",v[st[i]].x,v[st[i]].y);
return 0;
}