Cod sursa(job #1411084)

Utilizator T.C.11Tolan Cristian T.C.11 Data 31 martie 2015 13:57:49
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.62 kb
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");

vector<pair<double,double> > v,q;
vector<pair<double,double> >::iterator it;
pair<double,double> A,B;

int n,i;
double xMin,yMin,x,y;

bool cmp(pair<double,double> a, pair<double,double> b)
{
    if ((a.first-xMin)/(a.second-yMin)>(b.first-xMin)/(b.second-yMin))
        return true;
    else
        return false;
}

int main()
{
    fin>>n;
    fin>>xMin>>yMin;
    for (i=1;i<n;i++)
    {
        fin>>x>>y;
        if (y<yMin)
        {
            swap(y,yMin);
            swap(x,xMin);
        }
        else if (y==yMin)
        {
            if (x<xMin)
            {
                swap(y,yMin);
                swap(x,xMin);
            }
        }
        v.push_back(make_pair(x,y));
    }
    sort(v.begin(),v.end(),cmp);
    q.push_back(make_pair(xMin,yMin));
    it = v.begin();
    A = q.front();
    q.push_back(*it);
    v.erase(v.begin());
    for (vector<pair<double,double> >::iterator it = v.begin(); it != v.end(); it ++)
    {
        B = q.back();
        if ( (B.first-A.first)*((*it).second-A.second)-(B.second-A.second)*((*it).first-A.first) > 0) // ok
        {
            A=B;
            q.push_back(*it);
        }
        else //nu ok
        {
            q.pop_back();
            q.push_back(*it);
        }
    }
    fout<<q.size()<<"\n";
    for (vector<pair<double,double> >::iterator it = q.begin(); it != q.end(); it++)
        fout<<(*it).first<<" "<<(*it).second<<"\n";
    return 0;
}