Cod sursa(job #1579824)

Utilizator metrix007Lungu Ioan Adrian metrix007 Data 25 ianuarie 2016 09:22:05
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.4 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;
vector<punct> v;
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;
    A.x = INF;
    A.y = INF;
    v.push_back(A);
    for(int i=1;i<=n;i++)
    {
        in >> A.x >> A.y;
        v.push_back(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.begin()+1,v.begin()+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";
    for(int i=varf;i>=1;i--)
        out << setprecision(9) << stiva[i].x << " " << stiva[i].y << "\n";

    return 0;
}