Cod sursa(job #1148584)

Utilizator addy01adrian dumitrache addy01 Data 20 martie 2014 21:50:03
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.04 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 (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(v[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=v[1];
    int ind=1;
    for(i=2;i<=n;i++)
        {
            if( (v[i].x < first.x) || ( (v[i].x == first.x) && (v[i].y < first.y) ) )
                {
                    first=v[i];
                    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]=v[1];
    sol[2]=v[2];

    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--;

        sol[++nrp]=v[i];

    }

    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;
}