Pagini recente » Cod sursa (job #1048423) | Cod sursa (job #483618) | Cod sursa (job #1847504) | Cod sursa (job #2874593) | Cod sursa (job #2211121)
#include <stdio.h>
#include <iostream>
#include <algorithm>
#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;
}
bool compare(coordonate b, coordonate c)
{
return b.y<c.y;
}
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);
sort(v,v+n+1,compare);
primul.x=v[1].x; primul.y=v[1].y;
ultimul.x=v[n].x; ultimul.y=v[n].y;
v[1].pozitie=2;
v[n].pozitie=2;
for(i=1;i<=n;i++)
v[i].pozitie=arie(v[i]);
int numara=0;
int h1=1,h2=1;
stivadr[h1]=primul; numara++;
stivast[h2]=primul; numara++;
for(i=1;i<=n-1;i++)
{
if(v[i].pozitie==0)
{
while(stivadr[h1].x<v[i].x && h1>1)
{
h1--;
numara--;
}
h1++;
stivadr[h1]=v[i];
numara++;
}
else
{
while(stivast[h2].x>v[i].x && h2>1)
{
h2--;
numara--;
}
numara++;
h2++;
stivast[h2]=v[i];
}
}
h1++;
h2++;
stivadr[h1]=v[n]; numara++;
stivast[h2]=v[n]; numara++;
numara=numara-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;
}