Pagini recente » Cod sursa (job #782544) | Cod sursa (job #3133543) | Cod sursa (job #969482) | Cod sursa (job #968093) | Cod sursa (job #1756029)
#include <fstream>
using namespace std;
struct point {
double x,y,a;
} minp,a[120000],h[120000];
int n,m;
ifstream fin("infasuratoare.in");
ofstream out("infasuratoare.out");
void sw(point *x,point *y)
{
point q=*x;
*x=*y;
*y=q;
}
void qs(int le,int ri)
{
int i=le,j=ri; point p=a[(i+j)/2];
while (i<j)
{
while (a[i].a<p.a) i++;
while (a[j].a>p.a) j--;
if (i<=j)
{
sw(&a[i],&a[j]);
i++;
j--;
}
}
if (i<ri) qs(i,ri);
if (le<j) qs(le,j);
}
double ab(double x)
{
if (x<0) return x*-1; else return x;
}
void ca()
{
for (int i=1; i<=n; i++)
{
double c1=a[i].y-minp.y,c2=a[i].x-minp.x;
if ((c1==0) & (c2==0)) a[i].a=1.1;
else a[i].a=c1*ab(c1)/(c1*c1+c2*c2);
}
qs(1,n);
}
void lire()
{
fin >> n >> a[1].x >> a[1].y;
minp=a[1];
for (int i=2; i<=n; i++)
{
fin >> a[i].x >> a[i].y;
if ((minp.x>a[i].x) | (minp.x==a[i].x) & (minp.y<a[i].y))
minp=a[i];
}
ca();
}
double det(point a,point b,point c)
{
return a.x*b.y+b.x*c.y+c.x*a.y-a.x*c.y-b.x*a.y-c.x*b.y;
}
void hull()
{
m=3;
for (int i=1; i<=3; i++)
h[i]=a[i];
for (int i=4; i<=n; i++)
{
m++;
h[m]=a[i];
while ((m>2) & (det(h[m-2],h[m-1],h[m]) <=0))
{
h[m-1]=h[m];
m--;
}
}
out << m << endl;
for (int i=1; i<=m; i++)
out << h[i].x << " " << h[i].y << endl;
}
int main()
{
lire();
hull();
return 0;
}