Cod sursa(job #1092248)

Utilizator raulmuresanRaul Muresan raulmuresan Data 26 ianuarie 2014 19:26:43
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.84 kb
#include <fstream>
#include <algorithm>
#include<vector>
#include<stack>
#include<set>
#define inf 0x3f3f3f3f

using namespace std;

int i,n,k,j,p,s,unu,m,doi,q,dr,maxim,maxi2,val,cont,sol,z,ind[120009],orig,stiva[120009],vf;


struct punct
{
    double x,y;
}v[120010];


inline double panta(int a, int b)
{
    if(v[a].x==v[b].x)
        return inf;
    return (v[b].y-v[a].y)/(v[b].x-v[a].x);
};

struct cmp
{
    bool operator () (const int &a, const int &b)
    {
        return panta(a,orig)<panta(b,orig);
    }
};

inline double semn( int A, int B, int C ) {

    return ( double )v[ A ].x*v[ B ].y + v[ B ].x*v[ C ].y + v[ C ].x*v[ A ].y - v[ A ].y*v[ B ].x - v[ B ].y*v[ C ].x - v[ C ].y*v[ A ].x;
}


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




int main()
{

    fin>>n;
    orig=1;
    for(i=1;i<=n;++i)
    {
        fin>>v[i].x >>v[i].y;
        //cautam punctul cu x-ul cel mai mic...in caz de egalitate luam pnctul cu y minim
        if(v[i].x<v[orig].x || (v[i].x==v[orig].x && v[i].y<v[orig].y))
        {
            orig=i;
        }
        ind[i]=i;
    }
    //fout<<orig<<"\n";
    //sortare in functie de panta facuta cu cel mai din stanga punct
    sort(ind+1,ind+n+1,cmp());
    vf=1;
    stiva[vf]=orig;

    for( i = 1; i <= n; i++ ){
        if( ind[i] != orig ) {

            for( ; vf >= 2 && semn( stiva[ vf-1 ], stiva[ vf ], ind[ i ] ) < 0; --vf );
            stiva[ ++vf ] = ind[ i ];
        }
    }


    fout<<vf<<"\n";
    for(i=1;i<=vf;i++)
    {
        fout<<v[stiva[i]].x<<" "<<v[stiva[i]].y<<"\n";
    }
    //fout<<panta(orig,orig)<<" ";
    for(i=1;i<=n;i++)
    {
        //fout<<panta(ind[i],orig)<<" ";
    }
    //fout <<panta(2,orig);
    for(i=1;i<=n;i++)
    {
        //fout<<ind[i]<<" ";
    }
}