Pagini recente » Cod sursa (job #218168) | Cod sursa (job #2910970) | Cod sursa (job #3164831) | Cod sursa (job #37128) | Cod sursa (job #474225)
Cod sursa(job #474225)
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int n,i,point,stack[120005],nrs;
double x,y;
pair<double,double> v[120005];
struct cmp
{
inline bool operator()(const pair<double,double> &a,const pair<double,double> &b)const
{
if (a.first==x && a.second==y)
return 1;
if (b.first==x && b.second==y)
return 0;
if (a.first==x)
return 0;
if (b.first==x)
return 1;
return ((long double)(a.second-y)/(a.first-x)<(long double)(b.second-y)/(b.first-x));
}
};
inline bool dif(int dr1,int dr2,int punct)
{
if (v[dr1].first==v[dr2].first)
return (x<v[dr1].first && v[punct].first>v[dr1].first);
long double a,b,val1,valpct;
a=(long double)(v[dr1].second-v[dr2].second)/(v[dr1].first-v[dr2].first);
b=v[dr1].second-a*v[dr1].first;
val1=a*v[1].first+b-v[1].second;
valpct=a*v[punct].first+b-v[punct].second;
return (val1>0 && valpct<0) || (val1<0 && valpct>0);
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d %lf %lf",&n,&x,&y);
v[1]=make_pair(x,y);
point=1;
for (i=2;i<=n;++i)
{
scanf("%lf %lf",&x,&y);
v[i]=make_pair(x,y);
if (v[i].first<v[point].first || (v[i].first==v[point].first && v[i].second<v[point].second))
point=i;
}
x=v[point].first;
y=v[point].second;
sort(v+1,v+n+1,cmp());
nrs=1;
stack[1]=1;
for (i=2;i<=n;++i)
{
while (nrs>=3 && dif(stack[nrs],stack[nrs-1],i))
--nrs;
stack[++nrs]=i;
}
printf("%d\n",nrs);
for (i=1;i<=nrs;++i)
printf("%lf %lf\n",v[stack[i]].first,v[stack[i]].second);
return 0;
}