Pagini recente » Cod sursa (job #1183496) | Cod sursa (job #1179783) | Cod sursa (job #2585028) | Cod sursa (job #903288) | Cod sursa (job #1589910)
#include<fstream>
#include<cstdio>
#include <algorithm>
#define NMAX 130005
using namespace std;
struct punct
{
double x,y;
}v[NMAX],st[NMAX],X;
int n,i,k,poz;
double panta(punct a, punct b, punct c)
{
return a.x * b.y + b.x*c.y + c.x*a.y - b.y*c.x - c.y*a.x - b.x*a.y;
}
bool cmp(punct a,punct b)
{
return panta(v[1],a,b)<0;
}
int main()
{
ifstream f("infasuratoare.in");
freopen("infasuratoare.out","w",stdout);
f>>n;
f>>v[1].x>>v[1].y;
X.x=v[1].x;X.y=v[1].y;
poz=1;
for(i=2;i<=n;++i)
{
f>>v[i].x>>v[i].y;
if(v[i].y<X.y) {X=v[i];poz=i;}
else if (v[i].y == X.y && v[i].x<X.x) {X=v[i];poz=i;}
}
swap(v[poz],v[1]);
sort(v+2,v+n+1,cmp);
st[1]=v[1];st[2]=v[2];k=2;
for(i=3;i<=n;++i)
{
while(k >=2 && panta(st[k-1],st[k],v[i])>0) --k;
++k;
st[k]=v[i];
}
printf("%d\n",k);
for(i=k;i>=1;--i)
{
printf("%.9lf %.9lf\n",st[i].x,st[i].y);
}
return 0;
}