Cod sursa(job #972049)

Utilizator narcis_vsGemene Narcis - Gabriel narcis_vs Data 10 iulie 2013 21:26:40
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.61 kb
#include <stdio.h>
#include <vector>
#include <bitset>
#include <algorithm>

#define In "invasuratoare.in"
#define Out "invasuratoare.out"
#define Nmax 120010
#define eps 1e-12

using namespace std;

int N,St[Nmax], top;

pair<float,float> A[Nmax];
bitset< Nmax >use;

inline void Read()
{
    FILE * FIN = fopen(In,"r");
    fscanf(FIN,"%d",&N);
    for(int i = 1; i <= N; ++i)
        fscanf(FIN,"%f %f",&A[i].first,&A[i].second);
    fclose(FIN);
    sort(A+1,A+N+1);
}

inline float Semn(int i,int j,int k)
{
    return (A[j].first-A[i].first)*(A[k].second-A[i].second)-(A[j].second-A[i].second)*(A[k].first-A[i].first);
}

inline void Solve()
{
    int i,x = 1;
    St[++top] = 1;St[++top] = 2;
    use[1] = use[2] = true;
    for(i = 3 ;i!=1; i += x)
    {
        if(!use[i])
        {
            if(Semn(St[top-1],St[top],i) < eps)
            {
                use[St[top]] = 0;
                use[i] = 1;
                St[top] = i;
                while(top>=2 && Semn(St[top-1],St[top],i) < eps )
                {
                    use[St[top]] = 0;
                    --top;
                }
            }
            St[++top] = i;
            use[i] = 1;
        }
        if(i==N)
            x = -1;
    }
}

inline void Write()
{
    FILE * FOUT = fopen(Out,"wt");
    fprintf(FOUT,"%d\n",top);
    for(int i=2;i<=top;++i)
        fprintf(FOUT,"%.6lf %.6lf\n",A[St[i]].first,A[St[i]].second);
    fprintf(FOUT,"%.6lf %.6lf\n",A[St[1]].first,A[St[1]].second);
    fclose(FOUT);
}

int main()
{
    Read();
    Solve();
    Write();
    return 0;
}