Pagini recente » Cod sursa (job #578503) | Cod sursa (job #1895621) | Cod sursa (job #106421) | Cod sursa (job #3189288) | Cod sursa (job #1242899)
#include<cstdio>
#include<algorithm>
using namespace std;
pair <double,double> v[130000];
int i,s[130000],h,k,q,n;
double x,y;
bool ok[130000];
int semn(pair <int,int> a,pair<double,double> b,pair<double,double> c)
{
double x,y,z;
x=a.second-b.second;
y=b.first-a.first;
z=a.first*b.second-b.first*a.second;
x*=c.first;
y*=c.second;
x=x+y+z;
if(x+1e-12<0)
{
return -1;
}
if(x+1e-12>0)
{
return 1;
}
if(x+1e-12==0)
{
return 0;
}
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%lf%lf",&x,&y);
v[i]=make_pair(x,y);
}
sort(v+1,v+n+1);
ok[2]=true;
s[1]=1;
s[2]=2;
i=3;
q=1;
k=2;
while(ok[1]==false)
{
while(ok[i]==true)
{
if(i==n)
{
q=-1;
}
i+=q;
}
while(k>=2&&semn(v[s[k-1]],v[s[k]],v[i])==-1)
{
ok[s[k]]=false;;
k--;
}
s[++k]=i;
ok[i]=true;
}
h=k-1;
printf("%d\n",h);
for(i=2;i<=h+1;i++)
{
printf("%.6lf %.6lf\n",v[s[i]].first,v[s[i]].second);
}
return 0;
}