Pagini recente » Cod sursa (job #1687578) | Cod sursa (job #319400) | Cod sursa (job #809010) | Cod sursa (job #3188726) | Cod sursa (job #626379)
Cod sursa(job #626379)
#include <stdio.h>
#include <algorithm>
using namespace std;
#define nmax 120005
#define inf 1000000005
struct punct {double x, y;};
punct v[nmax], st[nmax], o;
long i, n, sf;
double difax, difay, difbx, difby, pa, pb;
void citire()
{
o.y=inf; o.x=inf;
scanf("%ld",&n);
for (i=1;i<=n;i++)
{
scanf("%lf %lf",&v[i].x,&v[i].y);
if ((v[i].x<o.x)||((v[i].x==o.x)&&(v[i].y<o.y)))
{o=v[i]; v[i]=v[1]; v[1]=o; }
}
}
bool cmp(punct a, punct b)
{
difay=a.y-o.y; difax=a.x-o.x;
difby=b.y-o.y; difbx=b.x-o.x;
if (difax==0)
pa=inf;
else
pa=difay/difax;
if (difay==0)
pa=0;
if (difbx==0)
pb=inf;
else
pb=difby/difbx;
if (difby==0)
pb=0;
return (pa<pb);
}
void rezolvare()
{
st[1]=v[1]; st[2]=v[2]; st[3]=v[3];sf=3;
for (i=4;i<=n;i++)
{
while ((sf>=3)&&(st[sf-1].x*st[sf].y + st[sf].x*v[i].y + v[i].x*st[sf-1].y - st[sf].y*v[i].x - v[i].y*st[sf-1].x - st[sf-1].y*st[sf].x<0))
sf--;
st[++sf]=v[i];
}
printf("%ld\n",sf);
for (i=2;i<=sf;i++)
printf("%lf %lf\n",st[i].x,st[i].y);
printf("%lf %lf\n",st[1].x,st[1].y);
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
citire();
sort(v+2,v+1+n,cmp);
rezolvare();
return 0;
}