Pagini recente » Cod sursa (job #481573) | Cod sursa (job #1268005) | Cod sursa (job #1176833) | Cod sursa (job #1775692) | Cod sursa (job #1650830)
#include <bits/stdc++.h>
using namespace std;
vector <int >st;
pair <double ,double >punc[120005];
int n;
void citire()
{
scanf("%d",&n);
for (int i=1;i<=n;++i)
scanf("%lf%lf",&punc[i].first,&punc[i].second);
}
double det(pair <double,double > a,pair <double,double > b,pair <double ,double >c)
{
return (b.first-a.first)*(c.second-a.second)-(b.second-a.second)*(c.first-a.first);
}
struct cmp{
bool operator ()(pair <double,double > a,pair < double ,double > b)
{
return det(punc[1],a,b)>0;
}
};
void sortare_trig()
{
int p=1;
for (int i=2;i<=n;++i)
if (punc[i]<punc[p])
p=i;
swap(punc[1],punc[p]);
sort(punc+2,punc+n+1,cmp());
}
void infasuratoare()
{
sortare_trig();
st.push_back(1);
st.push_back(2);
for (int i=3;i<=n;++i)
{
int siz=st.size();
while (siz>=2 && det(punc[st[siz-2]],punc[st[siz-1]],punc[i])<0)
{
--siz;
st.pop_back();
}
st.push_back(i);
}
int siz=st.size();
printf("%d\n",siz);
for (int i=0;i<siz;++i)
printf("%lf %lf\n",punc[st[i]].first,punc[st[i]].second);
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
citire();
infasuratoare();
return 0;
}