Pagini recente » Cod sursa (job #238353) | Cod sursa (job #2438951) | Cod sursa (job #2377676) | Cod sursa (job #37374) | Cod sursa (job #2172845)
#include <fstream>
#include <algorithm>
#include <iomanip>
#define nmax 120010
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct punct{
double x,y;
} a[nmax],stk[nmax],minim;
int n,i,poz,vf;
double delta(punct A, punct B, punct C)
{
return (B.x-A.x)*(C.y-A.y)-(B.y-A.y)*(C.x-A.x);
}
class cmp
{
public:
bool operator()(punct A, punct B)
{
return delta(a[1],A,B)<0;
}
};
int main()
{
fin >> n;
minim.x=minim.y=1000000010;
for (i=1; i<=n; i++)
{
fin >> a[i].x >> a[i].y;
if (a[i].x<minim.x||(a[i].x==minim.x&&a[i].y<minim.y))
minim=a[i],poz=i;;
}
swap(a[1],a[poz]);
sort(a+2,a+n+1,cmp());
stk[vf]=a[1];
stk[++vf]=a[2];
for (i=3; i<=n; i++)
{
while (vf>0&&delta(stk[vf-1],stk[vf],a[i])>0)
vf--;
stk[++vf]=a[i];
}
fout << vf+1 << '\n';
for (i=vf; i>=0; i--)
fout << fixed << setprecision(12) << stk[i].x << ' ' << stk[i].y << '\n';
}