Cod sursa(job #1827793)

Utilizator CTI_KnightCir Constantin CTI_Knight Data 12 decembrie 2016 12:48:27
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.11 kb
// CTI
// Infasuratoarea convexa

#include <iostream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <stack>

using namespace std;

ifstream f ("infasuratoare.in");
ofstream g ("infasuratoare.out");

class Point {
public:
    double x;
    double y;
};

Point x;
vector <Point> v;

double delta(Point p,Point q, Point r) {
    /*
    |q.x - p.x   r.x - p.x| - matricea
    |q.y - p.y   r.y - p.y|
    */
    double x = (q.x - p.x) * (r.y - p.y) - (r.x - p.x) * (q.y - p.y);
    return x;
}

bool compare(Point p, Point q) {

    double d = delta(x, p, q);
    if (d < 0) {
        return true;
    }
    return false;
}

void infasuratoareConvexa()
{
    // citim datele
    int n; f >> n;
    v.push_back(x); // push sa incepem de la 1
    for (int i = 1; i <= n; ++i) {
        Point Po;
        f >> Po.x >> Po.y;
        v.push_back(Po);

    }

    // aflam un punct care se afla sigur pe infasuratoare
    int k = 1;  // presupunem ca primul se afla
    for (int i = 2; i <= n; ++i) {
        if (v[k].x > v[i].x) {
            k = i;
        } else if (v[k].x == v[i].x && v[k].y > v[i].y) {
            k = i;
        }
    }

    swap(v[k], v[1]);
    x = v[1];

    sort (v.begin() + 1, v.end(), compare); // il lasam pe primul pe pozitia lui

    vector <Point> s;    // vector pentru a verfica daca punctele sunt pe infasuratoare
    s.push_back(x);      // se afla sigur pe infasuratoare
    s.push_back(v[2]);   // presupunem ca se afla pe infasuratoare

    for (int i = 3; i <= n; ++i) {
        int sz = s.size();
        x = v[i];
        if (sz >= 2 && delta(s[sz - 2], s[sz - 1], x) > 0) {    // viraj
            while (sz >= 2 && delta(s[sz - 2], s[sz - 1], x) > 0) {
                s.pop_back();
                sz = s.size();
            }
        }
        s.push_back(v[i]);
    }

    g << s.size() << '\n';

    for (int i = s.size() - 1; i >= 0; --i) {
        g << fixed << setprecision(12) << s[i].x << " " << s[i].y << '\n';
    }

}

int main()
{
    infasuratoareConvexa();

    return 0;
}