Pagini recente » Cod sursa (job #663791) | Cod sursa (job #2565091) | Cod sursa (job #706843) | Cod sursa (job #622076) | Cod sursa (job #3247514)
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
struct ura
{
double x,y;
short arie=0;
} v[120002],s[120002];
int cearie(double xa, double ya, double xb, double yb, double xc, double yc)
{
double ari;
ari=xa*yb+xb*yc+xc*ya-ya*xb-yb*xc-yc*xa;
if(ari<0)
return -1;
if(ari>0)
return 1;
return 0;
}
bool sortare(ura a, ura b)
{
if(a.x<b.x)
{
return true;
}
else if(a.x==b.x && a.y<b.y)
{
return true;
}
return false;
}
int main()
{
int n,vf=0;
cin>>n;
for(int i=1; i<=n; i++)
{
cin>>v[i].x>>v[i].y;
}
sort(v+1,v+n+1,sortare);
v[1].arie=0;
v[n].arie=0;
for(int i=2; i<n; i++)
{
v[i].arie=cearie(v[1].x,v[1].y,v[n].x,v[n].y,v[i].x,v[i].y);
}
s[++vf]=v[1];
for(int i=2; i<=n; i++)
{
if(v[i].arie<=0)
{
if(vf<2)
{
s[++vf]=v[i];
}
else
{
while(vf>=2 && cearie(s[vf-1].x,s[vf-1].y,s[vf].x,s[vf].y,v[i].x,v[i].y)==-1)
{
vf--;
}
vf++;
s[vf]=v[i];
}
}
}
int x=vf;
for(int i=n-1; i>0; i--)
{
if(v[i].arie>=0)
{
if(vf<=x+1)
{
s[++vf]=v[i];
}
else
{
while(vf>=x+1 && cearie(s[vf-1].x,s[vf-1].y,s[vf].x,s[vf].y,v[i].x,v[i].y)==-1)
{
vf--;
}
vf++;
s[vf]=v[i];
}
}
}
cout<<vf-1<<"\n";
for(int i=2; i<=vf; i++)
{
cout<<fixed<<setprecision(12)<<s[i].x<<" "<<s[i].y<<'\n';
}
return 0;
}