Cod sursa(job #559656)

Utilizator nautilusCohal Alexandru nautilus Data 17 martie 2011 23:03:37
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.39 kb
#include<fstream>
#include<stack>
#include<algorithm>
#define dmax 120010
using namespace std;

typedef struct punct
{
 double x,y;
} punct;
 

punct p[dmax];
int n,k;
int s[dmax];
bool v[dmax];

void citire()
{
 int i;
	
 ifstream fin("infasuratoare.in");
 
 fin>>n;
 for (i=1; i<=n; i++)
	 fin>>p[i].x>>p[i].y;
 
 fin.close();
}


bool comp(punct a, punct b)
{
 if (a.y == b.y)
	 return a.x < b.x; else
	 return a.y < b.y;
}


int aria(int a, int b, int c)
{
 if (p[a].x * p[b].y + p[c].x * p[a].y + p[b].x * p[c].y - p[c].x * p[b].y - p[a].x * p[c].y - p[b].x * p[a].y < 0)
	 return -1;
 
 return 0;	
}


void solve()
{
 int i;
	
 s[1] = 1; s[2] = 2;
 k = 2;
	
 for (i=3; i<=n; i++)
	 {
	  while (k > 1 && aria(s[k-1], s[k], i) < 0)
		  {
		   v[s[k]] = 0;
		   k--;
		  }
	  
	  k++;
	  s[k] = i;
	  v[i] = 1;
	 }
 
 for (i=n; i>=1; i--)
	 if (v[i] == 0)
		 {
		  while (k > 1 && aria(s[k-1], s[k], i) < 0)
		  {
		   v[s[k]] = 0;
		   k--;
		  }
	      
		  k++;
		  s[k] = i;
		  v[i] = 1;
		 }
}


void afisare()
{
 int i;
	
 ofstream fout("infasuratoare.out");
 
 fout<<k-1<<'\n';
 
 fout.setf(ios::fixed);
 fout.precision(6);
 
 for (i=1; i<=k-1; i++)
	 fout<<p[s[i]].x<<" "<<p[s[i]].y<<'\n';
 
 fout.close();
}


int main()
{
	
 citire();
 sort(p+1,p+n+1,comp);
 solve();
 afisare();
	
 return 0;
}