Cod sursa(job #1386662)

Utilizator roparexRoparex roparex Data 13 martie 2015 10:11:05
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.59 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;
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;
}