Cod sursa(job #1073261)

Utilizator tudorv96Tudor Varan tudorv96 Data 5 ianuarie 2014 21:03:33
Problema Infasuratoare convexa Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 2.12 kb
#include <vector>
#include <algorithm>
#include <cstdio>
using namespace std;

#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];

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

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

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

void Infasuratoare() {
    printf ("%d\n", S.size());
    for (int i = S.size()-1; i >= 0; --i)
        printf ("%.9lf %.9lf\n", S[i].first.first, S[i].first.second);
}

int main() {
    freopen ("infasuratoare.in", "r", stdin);
    freopen ("infasuratoare.out", "w", stdout);
    scanf ("%d\n", &n);
    int pos = 0;
    for (int i = 0; i < n; ++i) {
        punct p;
        scanf ("%lf %lf", &p.first.first, &p.first.second);
        p.second = i;
        P.push_back(p);
        if (P[pos] > P[i])
            pos = i;
    }
    swap (P[pos], P[0]);
    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]);
    }
    Infasuratoare();
    /*
    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;
   printf ("0 ");
    for (int i = Start; i != Start-1; i = (i + 1) % n)
        printf ("%d ", sol[i].NO);*/
}