Cod sursa(job #962484)

Utilizator P1gl3TGilca Mircea Alexandru P1gl3T Data 15 iunie 2013 13:11:21
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.48 kb
#include <cstdio>
 
#include <algorithm>
#include <fstream>
#include <iomanip>
#include <cmath>
#include <vector>
#include <iostream>
#include <cassert>
 
using namespace std;
 
#define x first
#define y second
 
typedef pair<double, double> Point;
 
//ifstream fin("H.in");
//ofstream fout("H.out");
 
const int MAX_N = 100000;
 
int n;

vector<Point> v;
 
vector<Point> stack;
int head;

ostream& operator<<(ostream& os, const Point &p) {
    os << "(" << p.x << ", " << p.y << ")";
    return os;
}
 
int read() {
    cin >> n;
    if (n == 0)
        return 0;
    v.resize(n);
    stack.resize(2 * n);
    for (int i = 0; i <  n; ++i)
        cin >> v[i].x >> v[i].y;
    return n;
}
 
inline double cross_product(const Point& A, const Point& B, const Point& C) {
    return (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x);
}
 
inline int cmp(const Point& p1, const Point& p2) {
    return cross_product(v[0], p1, p2) < 0;
}
 
void sort_points() {
    int pos = 0;
    for (int i = 1; i < n; ++i)
        if (v[i] < v[pos])
            pos = i;
    swap(v[0], v[pos]);
    //sort(v + 2, v + n + 1, cmp);
    sort(v.begin() + 1, v.end(), cmp);
}
 
void convex_hull() {
    sort_points();
 
    stack[0] = v[0];
    stack[1] = v[1];
    head = 1;
    for (int i = 2; i < n; ++i) {
        while (head >= 1 && cross_product(stack[head - 1], stack[head], v[i]) > 0)
            --head;
        stack[++head] = v[i];
    }
}
 
void write() {
    cout << fixed;
    cout << head << "\n";
    for (int i = head; i >= 0; --i)
        cout << setprecision(9) << stack[i].x << " " << stack[i].y << "\n";
}

inline double dist(Point &i, Point &j) {
    return (i.x - j.x) * (i.x - j.x) + (i.y - j.y) * (i.y - j.y);
}

void rot_cat() {
    v.resize(2*n);
    for (int i = 0; i < n; ++i) {
        v[n+i] = v[i];
    }

    int i = 0, j = 1;
    double d = 0, max = 0, dd;
    for (; i < n; ++i) {
        d = 0;
        for (;;++j) {
            assert(j < v.size());
            dd = dist(v[i], v[j]);
            //cout << v[i] << ", " << v[j] << " " << dd << endl;
            if (dd < d) {
                if (d > max)
                    max = d;
                break;
            }
            d = dd;
        }
    }
    //cout << setprecision(3) << sqrt(max) << endl;
    printf("%.2lf\n", sqrt(max));
}
 
int main() {
    freopen("infasuratoare.in", "r", stdin);
    freopen("infasuratoare.out", "w", stdout);
    //while(read()) {
    read();
        convex_hull();
        write();
        //rot_cat();
    //}
    return 0;
}