Cod sursa(job #1579852)

Utilizator metrix007Lungu Ioan Adrian metrix007 Data 25 ianuarie 2016 09:46:28
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.42 kb
#include <iostream>
#include <algorithm>
#include <fstream>
#include <iomanip>
#include <vector>
#define INF  999999
#define NMAX 120002
using namespace std;

struct punct
{
    double x,y;
}A,Min;
punct v[NMAX];
punct stiva[NMAX];
int k,n;
int sens(punct d0,punct d1, punct d2)
{
    return ((d1.x-d0.x)*(d2.y-d0.y) - (d2.x-d0.x)*(d1.y-d0.y));
}

int comp(punct a,punct b)
{
    return sens(v[1],a,b)<0;

}

int main()
{
    ifstream in("infasuratoare.in");
    ofstream out("infasuratoare.out");

    in >> n;
    for(int i=1;i<=n;i++)
    {
        in >> A.x >> A.y;
        v[i] = A;
    }

    Min.y = INF;

    for(int i=1;i<=n;i++)
    {

        if(v[i].y<Min.y)
        {

            k =i;
            Min = v[i];
        }
        if(v[i].y == Min.y && v[i].x<Min.x)
        {
            k = i;
            Min = v[i];
        }
    }
     swap(v[1],v[k]);
     sort(v+2,v+n+1,comp);
     stiva[1] = v[1];
     stiva[2] = v[2];
     int varf = 2;
     for(int i =3;i<=n;i++)
    {
        while(varf>=2 && sens(stiva[varf-1],stiva[varf],v[i])>0)
            varf--;
        stiva[++varf] = v[i];
     }

    out << fixed;
    out << varf << "\n";
    out << stiva[1].x << " "  << stiva[1].y << "\n";
    for(int i=varf;i>1;i--)
        out << setprecision(12) << stiva[i].x << " " << stiva[i].y << "\n";
    cout << stiva[1].x << " " <<stiva[1].y;
    return 0;
}