Pagini recente » Cod sursa (job #614011) | Cod sursa (job #708323) | Cod sursa (job #3169988) | Cod sursa (job #2462710) | Cod sursa (job #3245373)
#include <fstream>
#include <algorithm>
#include <stack>
#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];
stack<punct> s;
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"*/
punct punct1,punct2,punct3;
punct1=prim;
punct2=p1[1];
s.push(punct2);
for(int i=2;i<=cnt1;i++)
{
punct3=p1[i];
while(s.size()>=2 and arie(punct1,punct2,punct3)==-1)
s.pop();
s.push(punct3);
punct1=punct2;
punct2=punct3;
}
int cntd=0,c=s.size(),c1=c;
while(!s.empty())
{
cntd++;
drum[c]=s.top();
c--;
s.pop();
}
cntd++;
drum[cntd]=ult;
c1++;
punct1=ult;
punct2=p2[cnt2];
s.push(punct2);
for(int i=cnt2-1;i>=1;i--)
{
punct3=p2[i];
while(s.size()>=2 and arie(punct1,punct2,punct3)==-1)
s.pop();
s.push(punct3);
punct1=punct2;
punct2=punct3;
}
c=s.size();
while(!s.empty())
{
cntd++;
drum[c1+c]=s.top();
c--;
s.pop();
}
cntd++;
drum[cntd]=prim;
cout<<cntd<<"\n";
for(int i=1;i<=cntd;i++)
cout<<fixed<<setprecision(6)<<drum[i].x<<" "<<drum[i].y<<"\n";
return 0;
}