Pagini recente » Cod sursa (job #317780) | Cod sursa (job #2125054) | Cod sursa (job #2724443) | Cod sursa (job #1328787) | Cod sursa (job #1538266)
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int n,i;
double inf, xmin,ymin;
struct punct{
double x, y, tg;
} v[120001];
punct st[120001];
bool cmp(punct x, punct y){
return x.tg<y.tg;
};
double det(punct a, punct b, punct c)
{
double d=0;
d=d+ a.x * b.y + a.y * c.x + b.x * c.y - c.x * b.y - c.y * a.x - b.x * a.y;
return d;
}
int main()
{
inf=2000000000;
xmin=inf;
ymin=inf;
fin>>n;
for(i=1;i<=n;i++)
{
fin>>v[i].x>>v[i].y;
if(v[i].x<xmin) xmin=v[i].x, ymin=v[i].y;
else if(v[i].x==xmin) ymin=min(ymin, v[i].y);
}
for(i=1;i<=n;i++)
{
if(v[i].x==xmin && v[i].y==ymin) v[i].tg=-inf;
else if(v[i].x==xmin) v[i].tg=inf;
else v[i].tg=(v[i].y-ymin)/(v[i].x-xmin);
}
sort(v+1,v+n+1, cmp);
int stlev=0;
st[1]=v[1];
st[2]=v[2];
stlev=2;
for(i=3;i<=n;i++)
{
while(det(st[stlev-1],st[stlev],v[i])<0 )
--stlev;
++stlev;
st[stlev]=v[i];
}
fout<<stlev<<'\n';
for(i=1;i<=stlev;i++)
fout<<setprecision(12)<<fixed<<st[i].x<<" "<<st[i].y<<'\n';
return 0;
}