Cod sursa(job #752238)

Utilizator Daniel30daniel Daniel30 Data 28 mai 2012 10:31:35
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include <cstdio>
#include <algorithm>
#include <vector>
#define pdd pair <double,double>
#define x first
#define y second
#define NMAX 120005
using namespace std;
int n,k;
vector<pdd> a;
pdd st[NMAX];
pdd aux;
void cit()
{freopen("infasuratoare.in","rt",stdin);
 freopen("infasuratoare.out","wt",stdout);
 scanf("%d",&n);
 a.push_back(aux);
 for (register int i=1; i<=n; i++)
	{scanf("%lf%lf",&aux.x,&aux.y);
	 a.push_back(aux);}
}
inline int semn(pdd a,pdd b,pdd c)
{double A=a.y-b.y; double B=b.x-a.x;
 double C=a.x*b.y-b.x*a.y;
 return (A*c.x+B*c.y+C)<0;
}
void infas()
{st[++k]=a[1]; st[++k]=a[2];
 for (register int i=3; i<=n; i++)
	 {while (k>=2 && semn(st[k-1],st[k],a[i])) k--;
	  st[++k]=a[i];
	 }
 for (register int i=n-1; i>=1; i--)
	{while (k>=2 && semn(st[k-1],st[k],a[i])) k--;
		st[++k]=a[i];
	}
 //k--;
 printf("%d\n",k);
 for (register int i=2; i<=k; i++)
	printf("%lf %lf\n",st[i].x,st[i].y);
}
int main()
{cit();
 sort(a.begin(),a.end());
 infas();
 return 0;
}