Pagini recente » Cod sursa (job #1827802) | Cod sursa (job #622191) | Cod sursa (job #1817941) | Cod sursa (job #2122928) | Cod sursa (job #3246560)
#include <fstream>
#include <stack>
#include <iomanip>
#include <algorithm>
using namespace std;
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
const int MAX=120005;
struct ura
{
float x, y;
}v[MAX];
int s[MAX], ns, s2[MAX], ns2;
bool verif_jos(int i, int xa, int ya, int xb, int yb)
{
int xc=v[i].x, yc=v[i].y;
if((xa*yb+xb*yc+xc*ya)<(ya*xb+yb*xc+yc*xa))
{
return 1;
}
return 0;
}
bool cmp(ura a, ura b)
{
if(a.x>b.x)
return 0;
else if(a.x<b.x)
return 1;
if(a.y<b.y)
return 1;
return 0;
}
int main()
{
int n;
cin>>n;
for(int i=1; i<=n; i++)
{
cin>>v[i].x>>v[i].y;
}
sort(v+1, v+n+1, cmp);
float xa=v[1].x, ya=v[1].y, xb=v[n].x, yb=v[n].y;
ns+=2;
s[1]=1;
s[2]=n;
for(int i=2; i<n; i++)
{
if(verif_jos(i, xa, ya, xb, yb))
{
if(verif_jos(i, v[s[ns-1]].x, v[s[ns-1]].y, v[s[ns]].x, v[s[ns]].y))
{
while(ns>1 && verif_jos(i, v[s[ns-1]].x, v[s[ns-1]].y, v[s[ns]].x, v[s[ns]].y))
{
ns--;
}
ns++;
s[ns]=i;
}
else
{
ns++;
s[ns]=i;
}
}
}
ns2+=2;
s2[1]=n;
s2[2]=1;
for(int i=n-1; i>=1; i--)
{
if(!verif_jos(i, xa, ya, xb, yb))
{
if(!verif_jos(i, v[s2[ns2]].x, v[s2[ns2]].y, v[s2[ns2-1]].x, v[s2[ns2-1]].y))
{
while(ns2>1 && !verif_jos(i, v[s2[ns2]].x, v[s2[ns2]].y, v[s2[ns2-1]].x, v[s2[ns2-1]].y))
{
ns2--;
}
ns2++;
s2[ns2]=i;
}
else
{
ns2++;
s2[ns2]=i;
}
}
}
cout<<ns+ns2<<'\n';
cout<<fixed<<setprecision(6);
for(int i=2; i<=ns; i++)
{
cout<<v[s[i]].x<<" "<<v[s[i]].y<<'\n';
}
for(int i=1; i<=ns2; i++)
{
cout<<v[s2[i]].x<<" "<<v[s2[i]].y<<'\n';
}
cout<<v[s[1]].x<<" "<<v[s[1]].y;
return 0;
}