Pagini recente » Cod sursa (job #1403453) | Cod sursa (job #575408) | Cod sursa (job #786605) | Cod sursa (job #512600) | Cod sursa (job #891562)
Cod sursa(job #891562)
#include<fstream>
#include<algorithm>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int n,vf;
typedef struct {float x,y;}NOD;
NOD st[12005],p[12005];
void citire()
{
f>>n;
for (int i=1;i<=n;i++)
f>>p[i].x>>p[i].y;
}
bool cmp (NOD a, NOD b)
{
return ((a.y < b.y) || (a.y == b.y && a.x < b.x));
}
float det(NOD a, NOD b, NOD c)
{
return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}
void convex_hull()
{
sort(p+1,p+n+1,cmp);
st[1]=p[1];
st[2]=p[2];
vf=2;
int i;
for (i=3;i<=n;i++)
{ while (det(st[vf-1],st[vf],p[i])>0)
vf--;
st[++vf]=p[i];
}
for (i=n-1;i>=1;i--)
{
while (det(st[vf-1],st[vf],p[i])>0)
vf--;
st[++vf]=p[i];
}
}
void afis()
{
for (int i=vf;i>=2;i--)
g<<(float)st[i].x<<' '<<(float)st[i].y<<'\n';
}
int main()
{
citire();
convex_hull();
g<<vf<<'\n';
afis();
return 0;
}