Pagini recente » Cod sursa (job #1827152) | Cod sursa (job #2311333) | Cod sursa (job #2739756) | Cod sursa (job #2343022) | Cod sursa (job #3245405)
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream cin ("infasuratoare.in");
ofstream cout ("infasuratoare.out");
struct punct{
double x,y;
}v[12001],p1[12001],p2[12001],drum[12001],st[12001];
bool cmp(punct a,punct b)
{
if(a.x==b.x)
return a.y<b.y;
return a.x<b.x;
}
int arie(punct a,punct b,punct c)
{
double area=a.x*b.y+b.x*c.y+c.x*a.y-b.y*c.x-c.y*a.x-a.y*b.x;
if(area>0)
return 1;
else
return -1;
}
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
cin>>v[i].x>>v[i].y;
sort(v+1,v+1+n,cmp);
/// for(int i=1;i<=n;i++)
///cout<<v[i].x<<" "<<v[i].y<<"\n";
punct prim=v[1],ult=v[n];
int cnt1=0,cnt2=0;
for(int i=2;i<=n-1;i++)
{
///selectam punctele, sub dr -> p1 peste dr -> p2
if(arie(prim,ult,v[i])==-1)
cnt1++,p1[cnt1]=v[i];
else
cnt2++,p2[cnt2]=v[i];
}
///stiva pt alea de sub
/* for(int i=1;i<=cnt1;i++)
cout<<p1[i].x<<" "<<p1[i].y<<"\n";
cout<<"\n";
for(int i=1;i<=cnt2;i++)
cout<<p2[i].x<<" "<<p2[i].y<<"\n"*/
int k;
k=1;
st[k]=prim;
for(int i=1;i<=cnt1;i++)
{
while(k>1 and arie(st[k-1],st[k],p1[i])<0)
k--;
k++;
st[k]=p1[i];
}
k++;
int k2=k;
st[k]=ult;
for(int i=cnt2;i>=1;i--)
{
while(k>k2 and arie(st[k-1],st[k],p2[i])<0)
k--;
k++;
st[k]=p2[i];
}
cout<<k<<"\n";
for(int i=2;i<=k;i++)
cout<<fixed<<setprecision(6)<<st[i].x<<" "<<st[i].y<<"\n";
cout<<fixed<<setprecision(6)<<st[1].x<<" "<<st[1].y<<"\n";
return 0;
}