Pagini recente » Cod sursa (job #2102537) | Cod sursa (job #1047171) | Cod sursa (job #2134132) | Cod sursa (job #2479109) | Cod sursa (job #1922180)
#include <fstream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <stack>
#include <iomanip>
using namespace std;
ifstream fin("cuplaj.in");
ofstream fout("cuplaj.out");
struct punct
{
double x,y;
} a[120010],minim,st[120010];
double cp(punct A, punct B, punct C)
{
return (B.y-A.y)*(C.x-A.x)-(C.y-A.y)*(B.x-A.x);
}
class cmp
{
public:
bool operator()(punct A, punct B)
{
return cp(a[1],A,B)<0;
}
};
int n,i,j,vf,poz;
int main()
{
fin >> n;
minim.x=1000000100;
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());
st[1]=a[1];
st[2]=a[2];
vf=2;
for (i=3; i<=n; i++)
{
while (vf>0&&cp(st[vf-1],st[vf],a[i])>0) vf--;
st[++vf]=a[i];
}
fout << vf << '\n';
for (i=1; i<=vf; i++)
fout << fixed << setprecision(12) << st[i].x << ' ' << st[i].y << '\n';
fout << '\n';
}