Cod sursa(job #1073231)

Utilizator tudorv96Tudor Varan tudorv96 Data 5 ianuarie 2014 20:12:58
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 2.06 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <iostream>
#include <iomanip>
using namespace std;

ifstream fin ("infasuratoare.in");
ofstream fout ("infasuratoare.out");

#define X first.first
#define Y first.second
#define NO second

const int N = 1e3+5;

typedef pair <pair <double, double>, int> punct;
vector <punct> P, S, sol;
int n, MIN;
bool used[N];

punct make_punct(int x, int y, int i) {
    return make_pair(make_pair (x, y), i);
}

inline int cross (punct A, punct B, punct C) {
    return (B.X - A.X) * (C.Y - A.Y) - (C.X - A.X) * (B.Y - A.Y);
}

bool cmp(punct A, punct B) {
    return cross (P[0], A, B) < 0;
}

bool coord_cmp (punct A, punct B) {
    return A.first > B.first;
}

int main() {
    fin >> n;
    for (int i = 0; i < n; ++i) {
        double x, y;
        fin >> x >> y;
        P.push_back (make_punct(x, y, i));
        if (P[MIN] > P[i])
            MIN = i;
    }
    swap (P[0], P[MIN]);
    sort (P.begin()+1, P.end(), cmp);
    S.push_back (P[0]);
    S.push_back (P[1]);
    for (int i = 2; i < n; ++i) {
        while (S.size() > 1 && cross (S[S.size()-2], S[S.size()-1], P[i]) > 0)
            S.pop_back();
        S.push_back (P[i]);
    }
    fout << S.size() << "\n" << fixed << setprecision(9);
    for (vector <punct> :: reverse_iterator it = S.rbegin(); it != S.rend(); ++it)
        fout << it->X << " " << it->Y << "\n";
    /*int s = 0;
    for (vector <punct> :: iterator it = S.begin(); it->X <= (it+1)->X && it != S.end(); ++it) {
        sol.push_back(*it);
        used[it->NO] = 1;
        s++;
    }
    sol.push_back (S[s]);
    used[sol[s++].NO] = 1;
    for (vector <punct> :: iterator it = P.begin(); it != P.end(); ++it)
        if (!used[it->NO])
            sol.push_back (*it);
    sort (sol.begin()+s, sol.end(), coord_cmp);
    int Start = 0;
    for (int i = 0; i < n; ++i)
        if(!sol[i].NO)
            Start = (i + 1) % n;
    fout << 0 << " ";
    for (int i = Start; i != Start-1; i = (i + 1) % n)
        fout << sol[i].NO << " ";*/
}