Cod sursa(job #1076712)

Utilizator cristitamasTamas Cristian cristitamas Data 10 ianuarie 2014 15:10:57
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.78 kb
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

struct Coordonate
{
    double x,y;
}Puncte[120500];

int N;
int Viz[120500];
vector <int> S;

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

int cmp(Coordonate A, Coordonate B)
{
    return A.y<B.y || A.y==B.y && A.x<B.x;
}

void Citire()
{
    f>>N;
    for(int i=1;i<=N;++i)
        f>>Puncte[i].x>>Puncte[i].y;
    sort(Puncte+1,Puncte+N+1,cmp);
}


double Det(Coordonate A, Coordonate B, Coordonate C)
{

    return A.x*B.y+B.x*C.y+A.y*C.x-B.y*C.x-A.x*C.y-A.y*B.x;
}

void Rezolvare()
{
    S.push_back(1);
    S.push_back(2);
    Viz[2]=1;
    double R;
    for(int i=3;i<=N;++i)
    {
        R=Det(Puncte[S[S.size()-2]],Puncte[S[S.size()-1]],Puncte[i]);
        while(R<0)
        {
            if(S.size()<=2)
            {
                Viz[S.back()]=0;
                S.pop_back();
                break;
            }
            Viz[S.back()]=0;
            S.pop_back();
            R=Det(Puncte[S[S.size()-2]],Puncte[S[S.size()-1]],Puncte[i]);
        }
        S.push_back(i);
        Viz[i]=1;
    }
    for(int i=N;i>=1;--i)
    {
        if(!Viz[i])
        {
            R=Det(Puncte[S[S.size()-2]],Puncte[S[S.size()-1]],Puncte[i]);
            while(R<0)
            {
                if(S.size()<=2)
                    S.pop_back();
                S.pop_back();
                R=Det(Puncte[S[S.size()-2]],Puncte[S[S.size()-1]],Puncte[i]);
            }
            S.push_back(i);
        }
    }
}

int main()
{
    Citire();
    Rezolvare();
    fout<<S.size()<<"\n";
    for(int i=0;i<S.size();++i)
        fout<<Puncte[S[i]].x<<" "<<Puncte[S[i]].y<<"\n";
    f.close();
    fout.close();
    return 0;
}