Cod sursa(job #1148554)

Utilizator addy01adrian dumitrache addy01 Data 20 martie 2014 21:25:55
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.18 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;

ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
const int maxn = 120001;
int n;

struct point
{
    double x,y;
}sol[maxn],v[maxn];



inline double cross_product(const point &a, const point &b, const point &c)
{
    return (double) (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}

inline bool cmp (const point& a,const point&b)
{
    //return a.panta < b.panta;
    return cross_product(sol[1],a,b) < 0;
}


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


//gaseste primul element din infasuratoare
    point first;
    first.y=1<<30;
    first.x=1<<30;
    int ind;
    for(i=1;i<=n;i++)
        {
            if((v[i].y<first.y)||(v[i].y==first.y&&v[i].x<first.x))
                {
                    first.y=v[i].y;
                    first.x=v[i].x;
                    ind=i;
                }
            }

//in v[i].panta retinem panta punctului i fata de punctul de referinta (cel mai din stanga jos)
    swap(v[1],v[ind]);//punctul de referinta este pus primul in vector
/*    for(i=2;i<=n;i++)
        v[i].panta=(v[i].y-first.y)/(v[i].x-first.x);
*/
//sortez vectorul in functie de panta
    sort(v+2,v+n+1,cmp);

//primele 2 puncte din solutie
    sol[1].x=v[1].x;
    sol[1].y=v[1].y;
    sol[2].x=v[2].x;
    sol[2].y=v[2].y;
    int nrp=2;
    //incercam toate punctele ramase :
    //daca ultimele doua puncte bagate in solutie si punctul curent se duc la dreapta si avem mai mult sau egal de 2 puncte in solutie ( cele initiale )
    //scoatem din solutie ultimul punct adauga, pana cand am ramas la 2 elemente in solutie sau merg la stanga; in acest caz adaug la solutie punctul curent

    for(i=3;i<=n;i++)
    {
        while( nrp >= 2 && cross_product(sol[nrp-1],sol[nrp],v[i]) > 0 )
            nrp--;

        nrp++;
        sol[nrp].x=v[i].x;
        sol[nrp].y=v[i].y;
    }

    out<<nrp<<"\n";
    out<<fixed<<setprecision(6);
    out<<sol[1].x<<" "<<sol[1].y<<"\n";
    for(i=nrp;i>=2;i--)
        out<<sol[i].x<<" "<<sol[i].y<<"\n";


    return 0;
}