Pagini recente » Cod sursa (job #675539) | Cod sursa (job #135070) | Cod sursa (job #2858909) | Cod sursa (job #92234) | Cod sursa (job #2546593)
#include<bits/stdc++.h>
using namespace std;
inline double det(pair<int,int> a,pair<int,int> b,pair<int,int> c)
{
return a.first*b.second+b.first*c.second+c.first*a.second-c.first*b.second-a.first*c.second-b.first*a.second;
}
const int maxN=(120005);
pair<double,double> v[maxN];
bool cmp(pair<int,int> a,pair<int,int> b)
{
return det(v[1],a,b)>0;
}
int n,st[maxN],vf;
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d",&n);
int p=1;
for(int i=1;i<=n;i++)
{
scanf("%lf%lf",&v[i].first,&v[i].second);
if(v[i].first<v[p].first || (v[i].first==v[p].first && v[i].second<v[p].second)) p=i;
}
swap(v[1],v[p]);
sort(v+2,v+n+1,cmp);
st[++vf]=1;
st[++vf]=2;
for(int i=3;i<=n;i++)
{
while(vf>=2 && det(v[st[vf-1]],v[st[vf]],v[i])<0) vf--;
st[++vf]=i;
}
printf("%d\n",vf);
for(int i=1;i<=vf;i++)
printf("%.12f %.12f\n",v[st[i]].first,v[st[i]].second);
return 0;
}