Pagini recente » Cod sursa (job #3227507) | Cod sursa (job #1087537) | Cod sursa (job #344821) | Cod sursa (job #2695041) | Cod sursa (job #1809699)
#include<cstdio>
#define x first
#define y second
#define eps 1e-12
#define punct pair<double,double>
#include<vector>
#include<algorithm>
using namespace std;
punct a[120003];
int s[120003],i,n,k,q;
bool fol[120003];
bool semn(punct o,punct a,punct b)
{
return ((a.first-o.first)*(b.second-o.second)+(o.first-b.first)*(a.second-o.second)>eps);
}
bool cmp(punct a,punct b)
{
if(a.first>b.first)
{
return true;
}
if(a.first==b.first)
{
return (a.second>b.second);
}
return false;
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%lf%lf",&a[i].first,&a[i].second);
}
sort(a+1,a+n+1,cmp);
s[1]=1;
s[2]=2;
k=2;
q=1;
i=3;
fol[2]=true;
for(i=3;i>0;i+=q)
{
if(i==n)
{
q=-1;
}
while(semn(a[s[k-1]],a[s[k]],a[i])&&k>=2)
{
fol[s[k--]]=false;
}
s[++k]=i;
fol[i]=true;
}
printf("%d\n",k-1);
for(i=1;i<k;i++)
{
printf("%.6f %.6f\n",a[s[i]].first,a[s[i]].second);
}
return 0;
}