Pagini recente » Cod sursa (job #2494217) | Cod sursa (job #289271) | Cod sursa (job #284415) | Cod sursa (job #1710015) | Cod sursa (job #407484)
Cod sursa(job #407484)
#include<stdio.h>
#include<algorithm>
#include<math.h>
using namespace std;
int viz[120005],st[120005],n,i,b,k,ok;
struct sir
{
double x;
double y;
double tg;
};
sir p[120005],s;
int cmp(sir a,sir b)
{
if(fabs(a.tg-b.tg)<0.000001)
return a.x<b.x;
return a.tg<b.tg;
}
void swap(sir &a, sir &b)
{
sir c;
c=a;
a=b;
b=c;
}
double check(sir a, sir b, sir c)
{
double s=0;
s+=a.x*b.y;
s-=b.y*c.x;
s+=a.y*c.x;
s-=a.x*c.y;
s+=b.x*c.y;
s-=a.y*b.x;
if(s<=0)return 0;
return 1;
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d",&n);
s.x=s.y=2000000000;
for(i=1;i<=n;i++)
{
scanf("%Lf %Lf",&p[i].x,&p[i].y);
if(p[i].x<s.x||p[i].x==s.x&&p[i].y<s.y){s=p[i];b=i;}
}
swap(p[b],p[1]);
for(i=2;i<=n;i++)
p[i].tg=(p[i].y-s.y)/(p[i].x-s.x);
sort(p+2,p+n+1,cmp);
st[1]=1;st[2]=2;
k=2;
for(i=3;i<=n;i++)
{
while(!check(p[st[k-1]],p[st[k]],p[i]))
k--;
st[++k]=i;
}
printf("%d\n",k);
for(i=1;i<=k;i++)
printf("%0.6Lf %0.6Lf\n",p[st[i]].x,p[st[i]].y);
return 0;
}