Pagini recente » Cod sursa (job #1119359) | Cod sursa (job #2467868) | Cod sursa (job #153171) | Cod sursa (job #757712) | Cod sursa (job #2211093)
#include <stdio.h>
#include <iostream>
#define NMAX 120001
using namespace std;
struct coordonate
{
double x,y;
int pozitie;
};
coordonate v[NMAX];
coordonate primul,ultimul;
coordonate stivadr[NMAX],stivast[NMAX];
int arie(coordonate a)
{
float arie1;
int valid;
arie1=primul.x*ultimul.y+ultimul.x*a.y+a.x*primul.y-a.x*ultimul.y-primul.x*a.y-ultimul.x*primul.y;
if(arie1<0)
valid=0;
if(arie1>0)
valid=1;
return valid;
// valid == 0 dreapta;
// valid == 1 stanga;
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
int n,i;
scanf("%d", &n);
for(i=1;i<=n;i++)
scanf("%lf%lf", &v[i].x, &v[i].y);
bool ok = true;
while(ok)
{
ok=false;
for(i=1;i<=n-1;i++)
if(v[i].y>v[i+1].y)
{
swap(v[i],v[i+1]);
ok=true;
}
if(v[i].y==v[i+1].y&&v[i].x>v[i+1].x)
{
swap(v[i],v[i+1]);
ok=true;
}
}
primul.x=v[1].x; primul.y=v[1].y;
ultimul.x=v[n].x; ultimul.y=v[n].y;
for(i=1; i<=n;i++)
v[i].pozitie=arie(v[i]);
v[1].pozitie=2;
v[n].pozitie=2;
// in dreapta
int numara;
int h1=1,h2=1;
stivadr[h1]=primul;
stivast[h2]=primul;
for(i=1;i<=n-1;i++)
{
if(v[i].pozitie==0)
{
while(stivadr[h1].x<v[i].x && h1>1)
h1--;
h1++;
stivadr[h1]=v[i];
}
else
{
while(stivast[h2].x>v[i].x && h2>1)
h2--;
h2++;
stivast[h2]=v[i];
}
}
h1++;
h2++;
stivadr[h1]=v[n];
stivast[h2]=v[n];
numara=h2+h1-2;
printf("%d\n", numara);
for(i=1;i<=h1-1;i++)
printf("%f %f\n", stivadr[i].x, stivadr[i].y);
for(i=h2;i>=2;i--)
printf("%f %f\n", stivast[i].x, stivast[i].y);
return 0;
}