Pagini recente » Cod sursa (job #1248296) | Cod sursa (job #1067680) | Cod sursa (job #1625276) | Cod sursa (job #1149016) | Cod sursa (job #1193780)
#include <fstream>
#include <iomanip>
#include <algorithm>
#define lmax 120005
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
struct el
{
long double x,y;
}
v[lmax];
struct ell
{
long double x,y;
int ind;
}
s[lmax];
int comp(el e1,el e2)
{
if (e1.y!=e2.y)
return e1.y<e2.y;
return e1.x<e2.x;
}
int n,nr,i,a,b,c;
bool ap[lmax];
int main()
{
f>>n;
for (i=1;i<=n;i++)
f>>v[i].x>>v[i].y;
sort(v+1,v+n+1,comp);
s[1].x=v[1].x;
s[2].x=v[2].x;
s[1].y=v[1].y;
s[2].y=v[2].y;
s[1].ind=1;
s[2].ind=2;
nr=2;
for (i=3;i<=n;i++)
{
a=s[nr-1].y-s[nr].y;
b=s[nr].x-s[nr-1].x;
c=s[nr-1].x*s[nr].y-s[nr].x*s[nr-1].y;
while (a*v[i].x+b*v[i].y+c<0)
{
ap[s[nr].ind]=0;
nr--;
a=s[nr-1].y-s[nr].y;
b=s[nr].x-s[nr-1].x;
c=s[nr-1].x*s[nr].y-s[nr].x*s[nr-1].y;
}
nr++;
ap[i]=1;
s[nr].y=v[i].y;
s[nr].x=v[i].x;
s[nr].ind=i;
}
for (i=n;i>=3;i--)
if (!ap[i])
{
a=s[nr-1].y-s[nr].y;
b=s[nr].x-s[nr-1].x;
c=s[nr-1].x*s[nr].y-s[nr].x*s[nr-1].y;
while (a*v[i].x+b*v[i].y+c<0)
{
nr--;
a=s[nr-1].y-s[nr].y;
b=s[nr].x-s[nr-1].x;
c=s[nr-1].x*s[nr].y-s[nr].x*s[nr-1].y;
}
nr++;
s[nr].y=v[i].y;
s[nr].x=v[i].x;
}
g<<nr<<'\n';
for (i=1;i<=nr;i++)
g<<fixed<<setprecision(6)<<s[i].x<<" "<<s[i].y<<'\n';
f.close();
g.close();
}