Pagini recente » Cod sursa (job #1495497) | Cod sursa (job #569222) | Cod sursa (job #805121) | Cod sursa (job #415292) | Cod sursa (job #1644506)
#include <bits/stdc++.h>
using namespace std;
pair < double ,double > punc[120005];
int n;
vector <int> st;
double det(pair <double ,double > x,pair <double ,double > y, pair <double,double > z)
{
return ((y.first-x.first)*(z.second-x.second)-(y.second-x.second)*(z.first-x.first));
}
int cmp(pair <double,double > x,pair < double ,double >y)
{
return det(punc[1],x,y)>0;
}
void citire()
{
scanf("%d",&n);
for (int i=1; i<=n; ++i)
scanf("%lf%lf",&punc[i].first,&punc[i].second);
int p=1;
for (int i=2; i<=n; ++i)
if (punc[i]<punc[p])
p=i;
swap(punc[1],punc[p]);
sort(punc+1,punc+n+2,cmp);
st.push_back(1);
st.push_back(2);
}
void infasuratoare()
{
for (int i=3; i<=n; ++i)
{
int siz=st.size();
while (siz>=2 && det(punc[st[siz-1]],punc[st[siz-2]],punc[i])>0)
{
--siz;
st.pop_back();
}
st.push_back(i);
}
printf("%d\n",st.size());
for (int i=0; i<st.size(); ++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;
}