Cod sursa(job #1921445)

Utilizator vladbatalanBatalan Vlad vladbatalan Data 10 martie 2017 12:44:21
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 5.01 kb
#include <bits/stdc++.h>

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

const int oo = 0x3f3f3f3f;
const double eps = 0.0001;

struct punct
{
    int x, y;
    punct()
    {
        x=0;
        y=0;
    }
    punct(int x, int y):x(x), y(y) {}
};

struct triunghi
{
    punct A, B, C;
    triunghi(punct A, punct B, punct C):A(A), B(B), C(C) {}
    double arie()
    {
        return A.x*B.y + B.x*C.y + C.x*A.y - C.x*B.y - B.x*A.y - A.x*C.y;
    }
};

punct NR[120010];
vector<pair<double, int> > tg;
int n, start, nr_stiva, capat;
double xmin;
vector<int> stiva;
bitset<120010> in_stiva;

int main()
{
    fin >> n;
    xmin = oo;
    for(int i=1; i<=n; i++)
    {
        fin >> NR[i].x >> NR[i].y;
        if(NR[i].x < xmin)
        {
            xmin = NR[i].x;
            start = i;
        }
        else if(NR[i].x == xmin)
        {
            if(NR[i].y < NR[start].y)
            {
                start = i;
                xmin = NR[i].x;
            }
        }
    }
    NR[n+1] = NR[1];
    NR[n+2] = NR[2];
    for(int i=1; i<=n; i++)
    {
        if(i != start)
        {
            double tag;
            if(NR[i].x - NR[start].x < eps && NR[i].x - NR[start].x > -eps)
                tag = oo;
            else
                tag = (double)(NR[i].y - NR[start].y)/(double)(NR[i].x - NR[start].x);
            tg.push_back(make_pair(tag, i));
        }
    }
    sort(tg.begin(), tg.end());
//    for(auto it:tg)
//    {
//        cout<<NR[it.second].x << ' ' <<NR[it.second].y<<'\n';
//    }
    stiva.push_back(start);
    in_stiva[start] = 1;
    for(auto it:tg)
    {
        if(it.second != start)
        {
            stiva.push_back(it.second);
            in_stiva[it.second] = 1;
            break;
        }
    }
//    cout<<"Stiva mea contine punctele: ";
//    for(auto it2:stiva)
//    {
//        cout<<it2<< "("<<NR[it2].x<<","<<NR[it2].y<<") ";
//    }
//    cout<<'\n';
    nr_stiva = 2;
    for(auto it:tg)
    {
        if(it.second != start && !in_stiva[it.second])
        {
            stiva.push_back(it.second);
//            cout<<"Am ajuns in punctul "<<it.second << "("<<NR[it.second].x<<","<<NR[it.second].y<<")\n";
            in_stiva[it.second] = 1;
            nr_stiva ++;

//            cout<<"Stiva mea contine punctele: ";
//            for(auto it2:stiva)
//            {
//                cout<<it2<< "("<<NR[it2].x<<","<<NR[it2].y<<") ";
//            }
//            cout<<'\n';
            if(triunghi(NR[stiva[nr_stiva-3]], NR[stiva[nr_stiva-2]], NR[stiva[nr_stiva-1]]).arie() < 0)
            {
//                cout<<"\tArie negativa, stergem: ";
                capat = stiva.back();
                in_stiva[stiva.back()] = 0;
                stiva.pop_back();
                nr_stiva --;
                while(triunghi(NR[stiva[nr_stiva-2]], NR[stiva[nr_stiva-1]], NR[capat]).arie() < 0)
                {
                    in_stiva[stiva.back()] = 0;
//                    cout<<stiva.back() << "("<<NR[stiva.back()].x<<","<<NR[stiva.back()].y<<") ";
                    stiva.pop_back();
                    nr_stiva --;
                }
//                cout<<'\n';
                stiva.push_back(capat);
                in_stiva[capat] = 1;
                nr_stiva++;
            }
            else
            {
                if(triunghi(NR[stiva[nr_stiva-3]], NR[stiva[nr_stiva-2]], NR[stiva[nr_stiva-1]]).arie() < eps && triunghi(NR[stiva[nr_stiva-3]], NR[stiva[nr_stiva-2]], NR[stiva[nr_stiva-1]]).arie() > -eps)
                {
//                    cout<<"\tColiniar, stergem: ";
                    capat = stiva.back();
                    in_stiva[capat] = 0;
                    stiva.pop_back();
                    nr_stiva --;
                    while(nr_stiva >= 2)
                    {
                        if(triunghi(NR[stiva[nr_stiva-2]], NR[stiva[nr_stiva-1]], NR[capat]).arie() < eps && triunghi(NR[stiva[nr_stiva-2]], NR[stiva[nr_stiva-1]], NR[capat]).arie() > -eps)
                        {
                            in_stiva[stiva.back()] = 0;
//                            cout<<stiva.back() << "("<<NR[stiva.back()].x<<","<<NR[stiva.back()].y<<") ";
                            stiva.pop_back();
                            nr_stiva --;
                        }
                        else
                            break;
                    }
//                    cout<<'\n';
                    stiva.push_back(capat);
                    in_stiva[capat] = 1;
                    nr_stiva++;
                }
            }

//            cout<<"Stiva mea contine punctele: ";
//            for(auto it2:stiva)
//            {
//                cout<<it2<< "("<<NR[it2].x<<","<<NR[it2].y<<") ";
//            }
//            cout<<'\n';
        }
    }
    fout<<stiva.size()<<'\n';
    for(auto it:stiva)
    {
        fout<<NR[it].x <<' '<<NR[it].y<<'\n';
    }

    return 0;
}