Cod sursa(job #492461)

Utilizator MariusMarius Stroe Marius Data 14 octombrie 2010 17:19:58
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.54 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;
}

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

    FILE *fi = fopen(iname, "r");
    fscanf(fi, "%d", &n);
    for (int i = 0; i < n; ++ i)
        fscanf(fi, "%lf %lf", &x, &y), points.push_back(make_pair(x, y));
    fclose(fi);

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

    FILE *fo = fopen(oname, "w");
    fprintf(fo, "%d\n", stk.size());
    for (int i = 0; i < (int) stk.size(); ++ i)
        fprintf(fo, "%lf %lf\n", stk[i].first, stk[i].second);
    fclose(fo);

    return 0;
}