Cod sursa(job #492459)

Utilizator MariusMarius Stroe Marius Data 14 octombrie 2010 17:16:59
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.7 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

const char iname[] = "infasuratoare.in";
const char oname[] = "infasuratoare.out";


int turnsRight(pair <double, double> a, pair <double, double> b, pair <double, double> c) {
/*  b.first -= a.first, b.second -= a.second;
    c.first -= a.first, c.second -= a.second;
    return (b.first * c.second - b.second * c.first) < 0;
*/
    double c1 = a.second - b.second;
    double c2 = b.first - a.first;
    double c3 = a.first * b.second - a.second * b.first;
    double ecuation = c1 * c.first + c2 * c.second + c3;

    return (ecuation < 0);
}

int main(void) {
    int n;  double x, y;
    vector < pair <double, double> > points;

    ifstream in(iname);
    in >> n;
    for (int i = 0; i < n; ++ i)
        in >> x >> y, points.push_back(make_pair(x, y));
    in.close();

    sort(points.begin(), points.end());
    vector < pair <double, double> > stk;

    stk.push_back(points[0]), stk.push_back(points[1]);
    for (int i = 2; i < (int) points.size(); ++ i) {
        while (stk.size() > 1 && turnsRight(stk[stk.size() - 2], stk[stk.size() - 1], points[i]))
            stk.pop_back();
        stk.push_back(points[i]);
    }
    for (int i = (int) points.size() - 2; i >= 0; -- i) {
        while (stk.size() > 1 && turnsRight(stk[stk.size() - 2], stk[stk.size() - 1], points[i]))
            stk.pop_back();
        stk.push_back(points[i]);
    }
    stk.pop_back();

    ofstream out(oname);
    out << stk.size() << '\n';
    for (int i = 0; i < (int) stk.size(); ++ i)
        out << stk[i].first << ' ' << stk[i].second << '\n';
    out.close();

    return 0;
}