Cod sursa(job #1021731)

Utilizator varga13VarGaz13 varga13 Data 4 noiembrie 2013 09:49:00
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.77 kb
#include <fstream>
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <iomanip>
#define mx 120009
#define PLUS 1000000000
#define e 0.000000000001
#define float long double
using namespace std;

ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");

int n, LowestPoint,H;
pair<float,float> point[mx],stack[mx];
void Read();//
void SortPoints();
void Solve();
void Write();

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

inline float trig(pair<float,float>& A,const pair<float,float>& B, const pair<float,float>& C)
{
    return (B.first-A.first)*(C.second-A.second)-(B.second-A.second)*(C.first-A.first);
}
inline int comp(const pair<float,float>& A, const pair<float,float>& B)
{
    return trig(point[0],A,B)<e;
}

void Solve()
{
    stack[0]=point[0];
    stack[1]=point[1];
    H=2;
    for(int i=2;i<n;i++)
        {

            while(H>1 && trig(stack[H-1],stack[H],point[i])>e)
                --H;
            stack[++H]=point[i];
        }
}

void SortPoints()
{
    swap(point[0],point[LowestPoint]);
    sort(point+1,point+n,comp);
}

void Write()
{
    g<<H+1<<'\n';
    for(int i=H;i>=0;--i)
        g<<setprecision(12)<<stack[i].first<<'\t'<<stack[i].second<<'\n';
}

void Read()
{

    f>>n;
    for(int i=0;i<n;++i)
    {
        f>>point[i].first>>point[i].second;

       /* if(point[i].first<=point[LowestPoint].first)
            {
                if(point[i].first==point[LowestPoint].first)
                    LowestPoint=(point[i].second<point[LowestPoint].second)? i:LowestPoint;
                else
                    LowestPoint=i;
            }*/
        if(point[i]<point[LowestPoint])
            LowestPoint=i;

    }

}