Pagini recente » Cod sursa (job #2335306) | Cod sursa (job #356599) | Cod sursa (job #28101) | Cod sursa (job #152636) | Cod sursa (job #1211912)
#include<fstream>
#include<algorithm>
#include<iomanip>
using namespace std;
#define NMAX 120005
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct punct
{
double x,y;
} aux,a[NMAX],st[NMAX];
int n,p,k;
double det(punct A, punct B, punct C)
{
return (B.x-A.x)*(C.y-A.y)-(C.x-A.x)*(B.y-A.y);
}
bool cmp(punct A, punct B)
{
return (det(a[1],A,B)>0);
}
int main()
{
int i;
fin>>n;
for (i=1;i<=n;++i)
fin>>a[i].x>>a[i].y;
p=1;
for (i=2;i<=n;++i)
if (a[i].x<a[p].x) p=i;
aux=a[1], a[1]=a[p], a[p]=aux;
sort(a+2,a+n+1,cmp);
st[1]=a[1], st[2]=a[2], k=2;
for (i=3;i<=n;++i)
{
while (k>1 && det(a[i],st[k],st[k-1])>0)
--k;
st[++k]=a[i];
}
fout<<k<<"\n";
for (i=1;i<=k;++i)
fout<<setprecision(12)<<fixed<<st[i].x<<" "<<st[i].y<<"\n";
return 0;
}