Cod sursa(job #1386718)

Utilizator roparexRoparex roparex Data 13 martie 2015 10:47:40
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.73 kb
#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;
}