Cod sursa(job #2000615)

Utilizator lupulescu2001Lupulescu Vlad lupulescu2001 Data 14 iulie 2017 11:42:46
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.93 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];
double b[120005];
int main()
{
    int n,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];
    for(i=2;i<n;i++)
        for(j=i+1;j<=n;j++)
        if(a[i].second==a[1].second && a[j].second==a[1].second)
        {
            if(a[j].first-a[1].first>a[i].first-a[1].first)
            swap(a[i],a[j]);
        }
        else
            if((a[i].second-a[1].second)*(a[j].first-a[1].first)>(a[j].second-a[1].second)*(a[i].first-a[1].first))
                swap(a[i],a[j]);
                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';
}