Cod sursa(job #2003239)

Utilizator lupulescu2001Lupulescu Vlad lupulescu2001 Data 22 iulie 2017 13:03:35
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.81 kb
#include<fstream>
#include<iomanip>
#include<algorithm>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
pair <double,double> stiva[120003],a[120005];
int n;

    bool parametru (const pair <double,double> &c, const pair <double,double> &d) {
        if ((c.second-a[1].second)*(d.first-a[1].first)<(d.second-a[1].second)*(c.first-a[1].first)) return true;
        return false;
    }

double b[120005];

int main()
{
    int i,maxx=1000000003,maxy=1000000003,x,j,l=3;
    fin>>n;
    for(i=1;i<=n;i++)
    {
        fin>>a[i].first>>a[i].second;
        if(a[i].first<maxx)
        {
            maxx=a[i].first;
            maxy=a[i].second;
            x=i;
        }
        else
            if(a[i].first==maxx && a[i].second<maxy)
            {
                maxy=a[i].second;
                x=i;
            }
    }
    swap(a[1],a[x]);
    stiva[1]=a[1];
    sort(a+2,a+1+n,parametru);
                stiva[2]=a[2];
                i=3;
        while(i<=n)
        {

           if(stiva[l-1].first*a[i].second+a[i].first*stiva[l-2].second+stiva[l-2].first*stiva[l-1].second-stiva[l-2].first*a[i].second-stiva[l-1].first*stiva[l-2].second-a[i].first*stiva[l-1].second>0)
    {
        stiva[l].first=a[i].first;
        stiva[l].second=a[i].second;
        l++;
    }
    else
        if(stiva[l-1].first*a[i].second+a[i].first*stiva[l-2].second+stiva[l-2].first*stiva[l-1].second-stiva[l-2].first*a[i].second-stiva[l-1].first*stiva[l-2].second-a[i].first*stiva[l-1].second<0 && l-1>2)
    {
        i--;
        l--;
    }
        i++;
        }
        stiva[l]=stiva[1];
        fout<<l-1<<'\n';
        for(i=2;i<=l;i++)
            fout<<fixed<<setprecision(6)<<stiva[i].first<<" "<<fixed<<setprecision(6)<<stiva[i].second<<'\n';
}