Pagini recente » Cod sursa (job #1123376) | Cod sursa (job #1573774) | Cod sursa (job #2840247) | Cod sursa (job #2131776) | Cod sursa (job #1545880)
#include<iostream>
#include<fstream>
#include<algorithm>
#include<iomanip>
#define x first
#define y second
using namespace std;
typedef pair<double,double> point;
point st[120005],p,v[120005],aux;
double trig(point a,point b,point c)
{
// return (double)(b.x-a.x)*(b.y-a.y)-(c.x-a.x)*(c.y-a.y);
return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
}
bool cmp(point a, point b)
{
return(trig(v[1],a,b)<0);
}
int vf,i,n,poz,mini;
int main()
{
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
cin>>n;
for(i=1;i<=n;i++)
{
cin>>v[i].x>>v[i].y;
if(i==1)
{
poz=1;
mini=v[i].y;
}
else if(v[i].y<mini)
mini=v[i].y;
}
aux=v[poz];
v[poz]=v[1];
v[1]=aux;
sort(v+2,v+1+n,cmp);
st[1]=v[1];
vf=1;
for(i=2;i<=n;i++)
{
while(vf>1&&trig(st[vf-1],st[vf],v[i])>0)
vf--;
vf++;
st[vf]=v[i];
}
cout<<vf<<"\n" ;
for(i=vf;i>=1;i--)
{
cout<<fixed<<setprecision(6)<<st[i].x<<" "<<st[i].y<<"\n";
}
return 0;
}