Cod sursa(job #800760)

Utilizator pantaniMarco Pantani pantani Data 22 octombrie 2012 15:51:23
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.84 kb
#include <cstdio>
#include <cstring>
#include <cmath>

#include <algorithm>
#include <fstream>
#include <iostream>
#include <vector>

using namespace std;

const int N = 1005;
const int INF = 0x7fffffff;
const double MIN = 0.00001;

struct mosia {
    int x, y, d;

    bool operator<(const mosia& other) const {
        if (y != other.y)
            return y < other.y;
        return x < other.x;
    }

    friend ostream& operator<<(ostream& out, const mosia& _mosia) {
        return out << _mosia.x << " " << _mosia.y << " " << _mosia.d;
    }
};

int n, nr;
double prof[N];
mosia v[N], stack[N];
double d1[N][3], d2[N][3];


void read() {
    scanf("%d", &n);

    for (int i = 1; i <= n; ++i)
        scanf("%d%d%d", &v[i].x, &v[i].y, &v[i].d);
}

int cross_product(mosia a, mosia b, mosia c) {
    return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}

inline double sqr(double x) { return x * x; }

double dist(mosia a, mosia b) {
    return sqrt(sqr(a.x - b.x) + sqr(a.y - b.y));
}

bool comp(mosia a, mosia b) {
    int cross = cross_product(v[1], a, b);
    if (cross < 0) return false;
    if (cross > 0) return true;
    return dist(v[1], a) < dist(v[1], b);
}

void set_points() {
    int pos = 1;
    for (int i = 2; i <= n; ++i)
        if (v[i] < v[pos])
            pos = i;
    swap(v[pos], v[1]);

    sort(v + 2, v + n + 1, comp);
}

void infasuratoare() {
    set_points();
    
    int p = n;
    while (cross_product(v[1], v[n], v[p - 1]) == 0)
        --p;
    for (int i = p, j = n; i < j; ++i, --j)
        swap(v[i], v[j]);

    nr = 2;
    stack[1] = v[1];
    stack[2] = v[2];

    for (int i = 3; i <= n; ++i) {
        while (nr >= 2 && cross_product(stack[nr - 1], stack[nr], v[i]) < 0)
            --nr;
        stack[++nr] = v[i];
    }
}

inline double profit(mosia p, mosia p1, mosia p2) {
    return (double) dist(p1, p2) * p.d / 2;
}

inline double max(double a, double b) {
    if (a - b > MIN)
        return a;
    return b;
}

void set_profit() {
    prof[1] = profit(stack[1], stack[nr], stack[2]);
    prof[nr] = profit(stack[nr], stack[nr - 1], stack[1]);

    for (int i = 2; i < nr; ++i)
        prof[i] = profit(stack[i], stack[i - 1], stack[i + 1]);
}

double dinamica(double a[N][3], bool ok) {
    int begin = 2;

    if (ok) {
        a[1][1] = prof[1];
        a[2][0] = a[1][1];
        begin = 3;
    }

    for (int i = begin; i < nr; ++i) {
        a[i][1] = a[i - 1][0] + prof[i];

        a[i][0] = max(a[i - 1][0], a[i - 1][1]);
    }

    a[nr][0] = max(a[nr - 1][0], a[nr - 1][1]);
    if (!ok)
        a[nr][1] = a[nr - 1][0] + prof[nr];

    return max(a[nr][0], a[nr][1]);
}

int main() {
    freopen("mosia.in", "r", stdin);
    freopen("mosia.out", "w", stdout);

    read();

    infasuratoare();

    set_profit();

    double r1 = dinamica(d1, true), r2 = dinamica(d2, false);

    printf("%.6lf", max(r1, r2));

    return 0;
}