Cod sursa(job #1821012)

Utilizator anisiaiAnisia Iova anisiai Data 2 decembrie 2016 14:31:15
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.71 kb
#include <fstream>
#define e 0.000000000001
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <cmath>
#include <iomanip>

using namespace std;

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

double lst[120004][2],n,t;
int stp =-1 ,stk[120004];

double det(int a,int b,int c)
{
    return (lst[b][0]-lst[a][0])*(lst[c][1]-lst[a][1])-(lst[c][0]-lst[a][0])*(lst[b][1]-lst[a][1]);
}

bool cmp ( int a , int b )
{
    return det(0,a,b) < 0;
}

int main()
{
    fin>>n;
    for(int i=0; i<n; i++)
        fin>>lst[i][0]>>lst[i][1];
    for(int i=0; i<n; i++)
        if(lst[i][1] < lst[stp][1] || stp == -1)
            stp = i;
        else if(fabs(lst[i][1]-lst[stp][1]<e))
            if(lst[i][0]-lst[stp][0]<0)
                stp=i;

    t=lst[stp][0];
    lst[stp][0]=lst[0][0];
    lst[0][0] = t ;

    t=lst[stp][1];
    lst[stp][1]=lst[0][1];
    lst[0][1] = t ;
    ///sort( lst +1 , lst + n , cmp );
    for(int i=1; i<n-1; i++)
        for(int j=i+1; j<n; j++)
            if(det(0,i,j)>0)
            {
                t=lst[i][0];
                lst[i][0]=lst[j][0];
                lst[j][0] = t ;
                t=lst[i][1];
                lst[i][1]=lst[j][1];
                lst[j][1] = t ;
            }

    stk[0] = 0;
    stk[1] = 1;
    int sp = 1;
    for (int i = 2 ; i <n ; i++ )
    {
        while(sp>=1 && det(stk[sp-1],stk[sp],i)>0.0)
            sp--;
        stk[++sp] = i;
    }


    fout<<sp+1<<endl;

    for (int i = sp ; i >=0  ; i-- )
        fout<<fixed<<setprecision(6)<<lst[stk[i]][0]<<" "<<lst[stk[i]][1]<<endl;
        //printf("%lf %lf\n",lst[stk[i]][0] , lst[stk[i]][1]);

    return 0;
}