Cod sursa(job #1097983)

Utilizator RarRaresNedelcu Rares RarRares Data 4 februarie 2014 12:05:58
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.99 kb
#include <iostream>
#include <cstdio>
#include <queue>
#include <stack>
#include <cmath>
#include <vector>
#include <algorithm>
#define nmax 120005
#define infinit 0x3f3f3f3f

using namespace std;

struct punct
{
    float x, y;
};
punct puncte[nmax];
int n;
int pozstart; //pozitia elementului care nu trebuie introdus in coada de prioritati.




double rotatie(const punct& a, const punct& b, const punct& c)
{
    return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}

struct cmp
{
    bool operator()(const punct& a, const punct& b)
    {
        return rotatie(puncte[pozstart], a, b) > 0;
    }
};


void citire()
{
    scanf("%d\n", &n);
    int xmin = infinit, ymin = infinit;
    for(int i = 1; i <= n; ++i)
    {
        scanf("%f %f\n", &puncte[i].x, &puncte[i].y);
        if(puncte[i].x < xmin)
        {
            pozstart = i;
            xmin = puncte[i].x;
            ymin = puncte[i].y;
        }
        else
            if(puncte[i].x == xmin && puncte[i].y < ymin)
            {
                pozstart = i;
                xmin = puncte[i].x;
                ymin = puncte[i].y;
            }
    }

    swap(puncte[1], puncte[pozstart]);
//    for(int i = 1; i <= n; i++)
//        cout << puncte[i].x << ' ' << puncte[i].y << '\n';
//    cout << "\n\n";
    sort(puncte+2, puncte+n+1, cmp());

}

punct stiva[nmax];
int main()
{

    freopen("infasuratoare.in", "r", stdin);
    freopen("infasuratoare.out", "w", stdout);

    citire();


    stiva[1] = puncte[1];
    stiva[2] = puncte[2];
    int k = 2;
    for(int i = 3; i <= n; ++i)
    {
        while(rotatie(stiva[k-1], stiva[k], puncte[i]) < 0)
            k--;
        stiva[++k] = puncte[i];
    }
//    for(int i = 1; i <= n; i++)
//        cout << puncte[i].x << ' ' << puncte[i].y << '\n';

    cout << k << '\n';
    cout.precision(12);
    for(int i = 1; i <= k; i++)
        cout << stiva[i].x << ' ' << stiva[i].y << '\n';
    return 0;
}