Pagini recente » Cod sursa (job #1025453) | Cod sursa (job #501200) | Cod sursa (job #1481697) | Cod sursa (job #1248267) | Cod sursa (job #1193785)
#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],s[lmax];
int comp(el e1,el e2)
{
int m1=0,m2=0;
if (v[1].x-e1.x)
m1=(v[1].y-e1.y)/(v[1].x-e1.x);
if (v[1].x-e2.x)
m2=(v[1].y-e2.y)/(v[1].x-e2.x);
return m1<m2;
}
int n,nr,i,a,b,c;
int main()
{
f>>n>>v[1].x>>v[1].y;
for (i=2;i<=n;i++)
{
f>>v[i].x>>v[i].y;
if (v[i].x!=v[1].x)
{
if (v[i].y<v[1].y)
swap(v[1],v[i]);
}
else
if (v[i].x<v[1].x)
swap(v[1],v[i]);
}
sort(v+2,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;
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)
{
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();
}