Pagini recente » Cod sursa (job #2918334) | Cod sursa (job #1075401)
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
struct punct
{
double x,y;
}v[120010];
int st[120010],viz[120010];
int n,pas,i;
bool cmp(punct a,punct b)
{
if (a.y<b.y) return 1;
if (a.y==b.y &&a.x<b.x) return 1;
return 0;
}
void modif()
{
if(pas==1)
{
i++;
if(i==n) pas--;
}
else i--;
}
void coeficienti(punct a,punct b, double &aa,double &bb,double &cc)
{
aa=a.y-b.y;
bb=b.x-a.x;
cc=a.x*b.y-b.x*a.y;
}
int semn(punct a,punct b,punct c)
{
double aa,bb,cc;
coeficienti(a,b,aa,bb,cc);
if(aa*c.x+bb*c.y+cc<=0)
return -1;
return 1;
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%lf%lf",&v[i].x,&v[i].y);
sort(v+1,v+n+1,cmp);
pas=1;
st[1]=1;
st[2]=2;
viz[2]=1;
i=2;
int k=2;
while(i>1)
{
while(viz[i])
modif();
if(i==0) break;
while(k>1 && semn(v[st[k-1]],v[st[k]],v[i])==-1)
{
viz[st[k]]=0;
k--;
}
k++;
st[k]=i;
viz[i]=1;
}
printf("%d\n",k-1);
for(int i=1;i<k;i++)
printf("%lf %lf\n",v[st[i]].x,v[st[i]].y);
return 0;
}