Cod sursa(job #2171923)

Utilizator andrei232000Andrei Maria andrei232000 Data 15 martie 2018 14:11:21
Problema Infasuratoare convexa Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 5.2 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
#define prec 0.0000000000001
using namespace std;
typedef pair<long double, long double> Point;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
vector<Point> puncte;
vector<Point> infasuratoare, infasuratoare2;
int N, i;
long double auxX, auxY, t1, t2;
Point currentP;
bool sortY(Point a, Point b)
{
    return (a.first < b.first);
}
int main()
{
    fin>>N;
    for(i = 0; i < N; ++i)
    {
        fin>>auxX>>auxY;
        puncte.push_back(make_pair(auxY, auxX));
    }
    sort(puncte.begin(), puncte.end(), sortY);
    infasuratoare.push_back(puncte[0]);
    infasuratoare.push_back(puncte[1]);
    for(i = 2; i < N; ++i)
    {
        currentP = puncte[i];
        if(fabs(currentP.first - infasuratoare[infasuratoare.size() - 1].first) < prec)
        {
            if(currentP.second > infasuratoare[infasuratoare.size() - 1].second)
            {
                infasuratoare.pop_back();
                t1 = (currentP.second - infasuratoare[infasuratoare.size() - 2].second) / (currentP.first - infasuratoare[infasuratoare.size() - 2].first);
                t2 = (currentP.second - infasuratoare[infasuratoare.size() - 1].second) / (currentP.first - infasuratoare[infasuratoare.size() - 1].first);
                while(t1 < t2 && infasuratoare.size() > 1)
                {
                    infasuratoare.pop_back();
                    t1 = (currentP.second - infasuratoare[infasuratoare.size() - 2].second) / (currentP.first - infasuratoare[infasuratoare.size() - 2].first);
                    t2 = (currentP.second - infasuratoare[infasuratoare.size() - 1].second) / (currentP.first - infasuratoare[infasuratoare.size() - 1].first);
                }
                infasuratoare.push_back(currentP);
            }
        }
        else
        {
            t1 = (currentP.second - infasuratoare[infasuratoare.size() - 2].second) / (currentP.first - infasuratoare[infasuratoare.size() - 2].first);
            t2 = (currentP.second - infasuratoare[infasuratoare.size() - 1].second) / (currentP.first - infasuratoare[infasuratoare.size() - 1].first);
            while(t1 < t2 && infasuratoare.size() > 1)
            {
                infasuratoare.pop_back();
                t1 = (currentP.second - infasuratoare[infasuratoare.size() - 2].second) / (currentP.first - infasuratoare[infasuratoare.size() - 2].first);
                t2 = (currentP.second - infasuratoare[infasuratoare.size() - 1].second) / (currentP.first - infasuratoare[infasuratoare.size() - 1].first);
            }
            infasuratoare.push_back(currentP);
        }
    }
    infasuratoare2.push_back(puncte[N - 1]);
    infasuratoare2.push_back(puncte[N - 2]);
    for(i = N - 3; i > -1; --i)
    {
        currentP = puncte[i];
        if(fabs(currentP.first - infasuratoare2[infasuratoare2.size() - 1].first) < prec)
        {
            if(currentP.second < infasuratoare2[infasuratoare2.size() - 1].second)
            {
                infasuratoare2.pop_back();
                t1 = (currentP.second - infasuratoare2[infasuratoare2.size() - 2].second) / (currentP.first - infasuratoare2[infasuratoare2.size() - 2].first);
                t2 = (currentP.second - infasuratoare2[infasuratoare2.size() - 1].second) / (currentP.first - infasuratoare2[infasuratoare2.size() - 1].first);
                while(t1 < t2 && infasuratoare2.size() > 1)
                {
                    infasuratoare2.pop_back();
                    t1 = (currentP.second - infasuratoare2[infasuratoare2.size() - 2].second) / (currentP.first - infasuratoare2[infasuratoare2.size() - 2].first);
                    t2 = (currentP.second - infasuratoare2[infasuratoare2.size() - 1].second) / (currentP.first - infasuratoare2[infasuratoare2.size() - 1].first);
                }
                infasuratoare2.push_back(currentP);
            }
        }
        else
        {
            t1 = (currentP.second - infasuratoare2[infasuratoare2.size() - 2].second) / (currentP.first - infasuratoare2[infasuratoare2.size() - 2].first);
            t2 = (currentP.second - infasuratoare2[infasuratoare2.size() - 1].second) / (currentP.first - infasuratoare2[infasuratoare2.size() - 1].first);
            while(t1 < t2 && infasuratoare2.size() > 1)
            {
                infasuratoare2.pop_back();
                t1 = (currentP.second - infasuratoare2[infasuratoare2.size() - 2].second) / (currentP.first - infasuratoare2[infasuratoare2.size() - 2].first);
                t2 = (currentP.second - infasuratoare2[infasuratoare2.size() - 1].second) / (currentP.first - infasuratoare2[infasuratoare2.size() - 1].first);
            }
            infasuratoare2.push_back(currentP);
        }
    }
    fout<<infasuratoare.size() + infasuratoare2.size() - 2<<'\n';
    for(i = 0; i < infasuratoare.size(); ++i)
    {
        fout<<fixed<<setprecision(6)<<infasuratoare[i].second<<" "<<infasuratoare[i].first<<'\n';
    }
    for(i = 1; i < infasuratoare.size() - 1; ++i)
    {
        fout<<fixed<<setprecision(6)<<infasuratoare2[i].second<<" "<<infasuratoare2[i].first<<'\n';
    }
    fout.close();
    return 0;
}