Pagini recente » Cod sursa (job #798235) | Cod sursa (job #3124612) | Cod sursa (job #2835620) | Cod sursa (job #674114) | Cod sursa (job #1830960)
#include<iostream>
#include<fstream>
#include<algorithm>
#include<iomanip>
#define DX 120050
using namespace std;
fstream fin("infasuratoare.in",ios::in),fout("infasuratoare.out",ios::out);
int n;
struct str
{
double x,y;
};
str p[DX],r[DX];
double det(str p,str a,str b)
{
return p.x*a.y+b.x*p.y+a.x*b.y-b.x*a.y-p.x*b.y-a.x*p.y;
}
bool cmp(str a,str b)
{
return (det(p[0],a,b)>=0);
}
int main()
{
double x,y,mx=9999999,my=9999999;
int ind,i,n,lr;
fin>>n;
for(i=1;i<=n;i++)
{
fin>>x>>y;
p[i]={x,y};
if(mx>x || (mx==x && my>y))
{
mx=x;my=y;ind=i;
}
}
p[0]=p[ind]; p[ind]=p[n];
sort(p+1,p+n,cmp);
r[0]=p[0]; r[lr=1]=p[1];
for(i=2;i<n;i++)
{
while(lr>1 && det(r[lr-1],r[lr],p[i])<0)
{
lr--;
}
lr++;
r[lr]=p[i];
}
fout<<lr+1<<"\n"<<fixed;
for(i=0;i<=lr;i++)
{
fout<<setprecision(12)<<r[i].x<<" "<<setprecision(12)<<r[i].y<<"\n";
}
}