Pagini recente » Cod sursa (job #2349230) | Cod sursa (job #455354) | Cod sursa (job #553101) | Cod sursa (job #3203144) | Cod sursa (job #1386662)
#include<fstream>
#include<vector>
#include<utility>
#include<cmath>
#include<algorithm>
#include<iomanip>
#define Inf (1<<31-1)
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
pair<double,double> m;
int n;
double x,y;
double sin(pair<double,double> aux)
{
aux.first=aux.first-m.first;
aux.second=aux.second-m.second;
return aux.second/aux.first;
}
bool cmp(pair<double,double> x, pair<double,double> y)
{
float s1 = sin (x), s2 = sin (y);
return s1>s2||(s1==s2&&x.first<y.first);
}
bool leftTurn(pair<double,double> x1,pair<double,double> x2,pair<double,double> x3)
{
return (x1.first*x2.second+x2.first*x3.second+x3.first*x1.second-x2.second*x3.first-x3.second*x1.first-x1.second*x2.first) > 0;
}
vector<pair<double,double> > d,q;
int main()
{
fin>>n;
m.first = m.second = Inf;
for(int i=1;i<=n;i++)
{
fin>>x>>y;
if(x<m.first) m.first=x;
if(y<m.second) m.second=y;
d.push_back(make_pair(x,y));
}
sort(d.begin(),d.end(),cmp);
q.push_back(d[0]);
for(vector<pair<double,double> >::iterator i=d.begin()+1;i!=d.end();i++)
{
if(q.size()==1) q.push_back(*i);
else
{
while(q.size()>1&&leftTurn(q[q.size()-2],q[q.size()-1],*i))
q.pop_back();
q.push_back(*i);
}
}
fout<<q.size()<<"\n";
fout<<fixed;
for(vector<pair<double,double> >::iterator i=q.begin();i!=q.end();i++)
fout<<setprecision(6)<<i->first<<" "<<i->second<<"\n";
return 0;
}