Cod sursa(job #768280)

Utilizator batistaUPB-Oprea-Cosmin-Dumitru batista Data 16 iulie 2012 15:20:43
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.43 kb
#include<fstream>
#include<cmath>
#include<iomanip>
#include<algorithm>
#define pi 3.14159265358932
#define inf 2000000000
using namespace std;
struct pct{long double x,y,u;}v[120006];
int n,i,ind[120006],st[120006],k;
long double xjos=inf,yjos=inf;
long double unghi(pct a)
{
	long double x=a.x-xjos,y=a.y-yjos;
	if(x==0 && y>0)return pi/2;
	if(x==1 && y<0)return 3*pi/2;
	if(y==0 && x>0)return 0;
	if(y==0 && x<0)return pi;
	if(x>0 && y>0) return atan(y/x);
	if(x>0 && y<0) return 3*pi/2+atan(x/-y);
	if(x<0 && y>0) return pi-atan(y/-x);
	if(x<0 && y<0) return pi+atan(-y/-x);
	return 0;
}
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)<0;
}
int main()
{
	ifstream f("infasuratoare.in");ofstream g("infasuratoare.out");
	f>>n;
	for(i=1;i<=n;i++)
	{
	 f>>v[i].x>>v[i].y;
	 ind[i]=i;
	 if( v[i].y<yjos || (v[i].y==yjos && v[i].x<xjos) ) { xjos=v[i].x; yjos=v[i].y; }//calculez punctul de extrem jos
	}
	for(i=1;i<=n;i++) v[i].u=unghi(v[i]);
	sort(ind+1,ind+n+1,cmp);
	k=3; st[1]=ind[1]; st[2]=ind[2]; st[3]=ind[3];
	i=3;
	while(i<n)
	{
	  while( semn(v[st[k-2]],v[st[k-1]],v[st[k]]) )
	  {
		st[k-1]=st[k];
		st[k]=ind[++i];
	  }	
	 if(i<n)st[++k]=ind[++i];
	}
	g<<k<<'\n';
	for(i=1;i<=k;i++)g<<setprecision(7)<<v[st[i]].x<<' '<<setprecision(7)<<v[st[i]].y<<'\n';
	f.close();g.close();
return 0;}