Cod sursa(job #1076729)

Utilizator cristitamasTamas Cristian cristitamas Data 10 ianuarie 2014 15:18:04
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.8 kb
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

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

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

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

void Citire()
{
    cin>>N;
    for(int i=1;i<=N;++i)
        cin>>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()
{
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);
    Citire();
    Rezolvare();
    printf("%d\n",S.size()-1);
    for(int i=0;i<S.size()-1;++i)
        printf("%.6lf %.6lf\n", Puncte[S[i]].x,Puncte[S[i]].y);
    return 0;
}