Cod sursa(job #674185)

Utilizator kitzTimofte Bogdan kitz Data 5 februarie 2012 19:24:10
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 kb
#include <fstream>
#include <algorithm>
#define Nmax 120010
#define INF 1<<30
using namespace std;
ifstream f("infasuratoare.in"); ofstream g("infasuratoare.out");
int n,i,k,s[Nmax],poz;
struct punct {double x,y,panta;} v[Nmax],t,aux;
int cmp ( punct a, punct b)
{if(a.panta==b.panta) return a.x<b.x;
 return a.panta<b.panta;
}
int convex()
{punct a,b,c; double S;
 a=v[s[k-1]];
 b=v[s[k]];
 c=v[i];
 S=(a.x-c.x)*(b.y-a.y)+(a.x-b.x)*(a.y-c.y);
 if(S>0) return 1;
 return 0;
}
int main()
{f>>n;
 t.x=t.y=INF;
 for(i=1;i<=n;i++)
	{f>>v[i].x>>v[i].y; //scanf("%lf %lf",&v[i].x,&v[i].y);
	 if(v[i].x < t.x || v[i].x == t.x && v[i].y < t.y)
			t=v[i],poz=i;
	}
 aux=v[1]; v[1]=v[poz]; v[poz]=aux;
 for(i=2;i<=n;i++)
	v[i].panta = (v[i].y -t.y)/(v[i].x-t.x);
 sort(v+2,v+n+1,cmp);
 s[1]=1; s[2]=2; k=2;
 for(i=3;i<=n;i++)
	{while ( !convex() && k>2 ) k--;
	 s[++k]=i;
	}
 g<<k<<"\n"; //printf("%d\n",k);
 g.precision(6);
 for(i=1;i<=k;i++)
		g<<v[s[i]].x<<" "<<v[s[i]].y<<"\n";//printf("%0.6lf %0.6lf\n",v[s[i]].x,v[s[i]].y);
 return 0;
}