Cod sursa(job #1337132)

Utilizator Miruna_DMiruna Miruna_D Data 8 februarie 2015 17:03:36
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.4 kb
#include <iostream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#define Nmax 120005
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int pozmin=0,head;
struct punct
{
    double x,y;
};
punct p[Nmax],s[Nmax];
int n;


void read()
{
    fin>>n;

    int i;

    p[0].y=10000000000;
    p[0].x=10000000000;
    for(i=1;i<=n;i++)
    {
        fin>>p[i].x;
        fin>>p[i].y;
        if(p[i].y<p[pozmin].y) pozmin=i;
        else
            if(p[i].y==p[pozmin].y)
                if(p[i].x<p[pozmin].x) pozmin=i;
    }

    swap(p[pozmin],p[1]);

}

int determinant(double x1, double y1, double x2, double y2, double x3, double y3)
{
        double det;
        det=x1*y2+x2*y3+x3*y1-x1*y3-x2*y1-x3*y2;
        return det;
}

int cmp(punct p1,punct p2)
{
    return (determinant(p[1].x,p[1].y,p1.x,p1.y,p2.x,p2.y)) >0;
}

void solve()
{

    s[1]=p[1];
    s[2]=p[2];
    head=2;

    for(int i=3;i<=n;i++)
    {
         while(head>=2 && determinant(p[i].x,p[i].y, s[head].x,s[head].y, s[head-1].x,s[head-1].y) > 0)
            head--;

           s[++head]=p[i];
    }


}
int main()
{
    read();
    sort(p+2,p+n+1, cmp);
    solve();

    fout<<head<<" \n";
   while(head)
   {
       fout<<fixed<<setprecision(12)<<s[head].x<<" "<<s[head].y<<"\n";
       head--;
   }

    return 0;
}