Cod sursa(job #1154232)

Utilizator narcis_vsGemene Narcis - Gabriel narcis_vs Data 26 martie 2014 01:11:29
Problema Oypara Scor 0
Compilator cpp Status done
Runda Lista lui wefgef Marime 1.29 kb
#include <stdio.h>
#include <vector>
#include <bitset>
#include <algorithm>
 
#define In "infasuratoare.in"
#define Out "infasuratoare.out"
#define Nmax 120010
#define eps 1e-12
using namespace std;
 
int N,St[Nmax], top;
 
pair<double,double> 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,"%lf %lf",&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[2] = true;
    for(i = 3 ;i>0; i += x)
    {
        if(!use[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-1);
    for(int i=1;i<top;++i)
        fprintf(FOUT,"%.6lf %.6lf\n",A[St[i]].first,A[St[i]].second);
    fclose(FOUT);
}
 
int main()
{
    Read();
    Solve();
    Write();
    return 0;
}