Cod sursa(job #768305)

Utilizator batistaUPB-Oprea-Cosmin-Dumitru batista Data 16 iulie 2012 16:19:42
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 kb
#include<cstdio>
#include<cmath>
#include<iomanip>
#include<algorithm>
#define pi 3.14159265358932
#define inf 2000000000
using namespace std;
struct pct{double x,y,u;}v[120006];
int n,i,ind[120006],st[120006],k,stp;
double xjos=inf,yjos=inf;
double unghi(pct a)
{ 
	double x=a.x-xjos,y=a.y-yjos;
	return (double)atan(y/x);
}
bool cmp(int i,int j)
{return v[i].u<v[j].u;
}
bool semn(pct a,pct b,pct c)//returneaza semnul determinantului
{
	return (a.x-b.x)*(b.y-c.y)<=(a.y-b.y)*(b.x-c.x);
}
int main()
{
	freopen("infasuratoare.in","r",stdin);freopen("infasuratoare.out","w",stdout);
	scanf("%d\n",&n);
	for(i=1;i<=n;i++)
	{
	 scanf("%lf %lf",&v[i].x,&v[i].y);
	 ind[i]=i;
	 if( v[i].x<xjos || (v[i].x==xjos && v[i].y<yjos) ) { xjos=v[i].x; yjos=v[i].y; stp=i; }//calculez punctul de extrem jos
	}
	v[stp].u=-inf;
	for(i=1;i<=n;i++) if(i!=stp)v[i].u=unghi(v[i]);
	sort(ind+1,ind+n+1,cmp);
	k=2;i=4; st[1]=ind[2]; st[2]=ind[3];
	while(i<=n)
	{
	  while( semn (v[st[k-1]] ,v[st[k]] ,v[ind[i]] ) ) k--;
	  st[++k]=ind[i++];
	}
	printf("%d\n",k+1);
	printf("%lf %lf\n",v[stp].x,v[stp].y);
	for(i=1;i<=k;i++) printf("%lf %lf\n",v[st[i]].x,v[st[i]].y);
return 0;}