Cod sursa(job #573159)

Utilizator okros_alexandruOkros Alexandru okros_alexandru Data 5 aprilie 2011 22:58:01
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.19 kb
using namespace std;
#include<fstream>
#include<algorithm>
struct punct{double x,y,panta;}v[120100],mx;
int ind[120100],st[120100],nr,vf;
bool cmp(punct a,punct b)
{return a.panta<b.panta;}
int verificare(int i)
{double a,b,c,d;
a=v[st[i-2]].x-v[st[i-1]].x;
b=v[st[i-2]].y-v[st[i-1]].y;
c=(v[st[i]].x-v[st[i-1]].x)*b;
d=(v[st[i]].y-v[st[i-1]].y)*a;
c-=d;
if(c<=0)
	return 0;
return 1;
}
inline void pop()
{st[--vf]=0;}
inline void push(int w)
{st[vf++]=w;}
int main()
{int n,i,j,k;
double a,b,r=-9999999;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
in>>n;
mx.x=mx.y=9999999;
for(i=0;i<n;i++)
	{in>>v[i].x>>v[i].y;
	if(v[i].x<mx.x||(v[i].x==mx.x&&v[i].y<mx.y))
		{mx.x=v[i].x;
		mx.y=v[i].y;
		k=i;
		}
	}
in.close();
for(i=0;i<n;i++)
	{a=mx.y-v[i].y;
	b=mx.x-v[i].x;
	if(b==0)
		ind[nr++]=i;
	else
		{v[i].panta=a/b;
		r=max(r,v[i].panta);
		}
	}
for(i=0;i<nr;i++)
	v[ind[i]].panta=r+1;
v[k].panta=r+2;
sort(v,v+n,cmp);
push(n-1);
push(0);
for(i=1;i<n-1;i++)
	{push(i);
	while(!verificare(vf-1))
		pop(),pop(),push(i);
	}
out<<vf<<'\n';
j=n-1;
for(i=0;i<vf;i++)
	out<<v[st[i]].x<<" "<<v[st[i]].y<<'\n';
out.close();
return 0;
}