Pagini recente » Cod sursa (job #812011) | Cod sursa (job #927702) | Cod sursa (job #1992142) | Cod sursa (job #250257) | Cod sursa (job #528193)
Cod sursa(job #528193)
#include <fstream>
#define NMAX 120012
using namespace std;
struct puncte{
double x,y;
double m;
} 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(float 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 0;
return 1;
}
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);
/*for(i=1;i<k;i++)
for(j=i+1;j<=k;j++)
{
e=panta(x,y, a[i].x,a[i].y, a[j].x,a[j].y);
if(e==1)
aux=a[i], a[i]=a[j], a[j]=aux;
else
if(e==-1&&a[i].x>a[j].x)
aux=a[i], a[i]=a[j], a[j]=aux;
}
for(i=0;i<=k;i++)
cout<<a[i].x<<" "<<a[i].y<<"\n";
cout<<endl;*/
st[st[0]=1]=0;
for(i=1;i<=k;i++)
{
while(!e_convex(a[st[st[0]]].x, a[st[st[0]]].y, a[st[st[0]-1]].x, a[st[st[0]-1]].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;
}