Cod sursa(job #483050)

Utilizator cosmyoPaunel Cosmin cosmyo Data 6 septembrie 2010 18:58:52
Problema Infasuratoare convexa Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.31 kb
#include<fstream>

#include<vector>
#include<algorithm>
#define x first
#define y second
#define NMAX 120005
using namespace std;
vector<long> st;
vector< pair<double,double> > p(NMAX);
pair<double,double> w;
long n;
void cit()
{ifstream fin("infasuratoare.in");
  fin>>n;
  long i;
   for( i=1;i<=n;++i)
	   fin>>p[i].x>>p[i].y;
   long o;
   o=1;
    for(i=2;i<=n;++i)
		if((p[o].y>p[i].y)||(p[o].y==p[i].y&&p[o].x>p[i].x))
			o=i;
   w=p[o];
   --n;
   p.erase(p.begin()+o);
   p[0]=w;
 fin.close();
}
int cmp(pair<double,double> a,pair<double,double> b)
{return (a.y-w.y)*(b.x-w.x)<(a.x-w.x)*(b.y-w.y);}
int sign(long i,long j,long k)
{return ((p[i].x-p[j].x)*(p[j].y-p[k].y)+(p[j].y-p[i].y)*(p[j].x-p[k].x))>0;}
ofstream fout("infasuratoare.out");
void solve()
{sort(p.begin()+1,p.begin()+n+1,cmp);
 long i;
 st.push_back(0);
 st.push_back(1);
  for(i=2;i<=n;++i)
  { while(st.size()>2&&!sign(st[st.size()-2],st[st.size()-1],i))
	   st.pop_back();
   st.push_back(i);
  }
}
void afis()
{  
 fout<<st.size()<<'\n';
  fout.precision(10);
  fout<<p[st[st.size()-1]].x<<" "<<p[st[st.size()-1]].y<<'\n';
  for(long i=0;i<st.size()-1;++i)
  {fout.precision(10);
   fout<<p[st[i]].x<<" "<<p[st[i]].y<<'\n';
  }
 fout.close();
}
int main()
{cit();
 solve();
 afis();
 return 0;
}