Pagini recente » Cod sursa (job #2054009) | Cod sursa (job #677809) | Cod sursa (job #1672291) | Cod sursa (job #1069184) | Cod sursa (job #1386718)
#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;
inline double sinus ( pair<double,double> p1, pair<double,double> p2 ) {
if ( p1.first == p2.first && p1.second == p2.second ) return Inf;
return (p2.second-p1.second)/(p2.first-p1.first);
}
bool cmp(pair<double,double> p1, pair<double,double> p2)
{
return sinus(m, p1) > sinus(m, p2);
}
inline bool leftTurn ( pair<double,double> p1, pair<double,double> p2, pair<double,double> p3 ) {
if ( p1.first == p2.first )
return ( p2.second - p1.second ) * ( p2.first - p3.first ) > 0;
else {
double m = ( p2.second - p1.second ) / ( p2.first - p1.first ),
n = p1.second - m * p1.first;
return ( p2.first - p1.first ) * ( p3.second - ( m * p3.first + n ) ) > 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;
d.push_back(make_pair(x,y));
if(x<m.first || (x == m.first && y<m.second)) m.first=x,m.second = 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++)
{
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.end()-1;i!=q.begin()-1;i--)
fout<<setprecision(6)<<i->first<<" "<<i->second<<"\n";
return 0;
}