Pagini recente » Cod sursa (job #2832654) | Cod sursa (job #1843962) | Cod sursa (job #1869304) | Cei mai harnici utilizatori info-arena | Cod sursa (job #528310)
Cod sursa(job #528310)
#include <fstream>
#define NMAX 120012
using namespace std;
struct puncte{
double x,y;
} a[NMAX];
int i,st[NMAX],n,k;
double x,y,xo,yo;
bool cmp(puncte x,puncte y)
{
return (double)(x.x - a[0].x) * (y.y - a[0].y) > (double)(y.x - a[0].x) * (x.y - a[0].y);
}
inline int e_convex(double x1, float y1, float x2, float y2, float x3, float y3)
{
double d;
d=(float)x1*y2+x2*y3+x3*y1-x2*y1-x3*y2-x1*y3;
if(d>0) return 1;
return 0;
}
int main()
{
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
f>>n;
f>>xo>>yo;
for(i=2;i<=n;i++)
{
f>>x>>y;
if(y<yo) a[++k].x=xo, a[k].y=yo, xo=x, yo=y;
else
if(y==yo&&x<xo) a[++k].x=xo, a[k].y=yo, xo=x, yo=y;
else
a[++k].x=x, a[k].y=y;
}
a[0].x=xo;
a[0].y=yo;
sort(a+1,a+k+1,cmp);
st[st[0]=1]=0;
for(i=1;i<=k;i++)
{
while((!e_convex(a[st[st[0]-1]].x, a[st[st[0]-1]].y, a[st[st[0]]].x, a[st[st[0]]].y,a[i].x,a[i].y))&&st[0]>=2) st[0]--;
st[++st[0]]=i;
}
g<<st[0]<<"\n";
for(i=1;i<=st[0];i++)
g<<a[st[i]].x<<" "<<a[st[i]].y<<"\n";
f.close();
g.close();
return 0;
}