Cod sursa(job #1589818)

Utilizator serbanSlincu Serban serban Data 4 februarie 2016 14:38:29
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 3.04 kb
#include <bits/stdc++.h>

using namespace std;

struct punct{
int x, y, d;
double tg;
};
punct mn, v[1005];
double dp[1005][2];
bool luat[1005][2];

double det(punct A, punct B, punct C) {
    return (A.x - B.x) * (C.y - B.y) - (A.y - B.y) * (C.x - B.x);
}

bool cmp(punct a, punct b) {
    return (det(a, mn, b) > 0);
}

int main()
{
    ifstream f("mosia.in");
    FILE *g = fopen("mosia.out", "w");
    mn.x = 10000, mn.y = 10000;
    int n; f >> n;
    for(int i = 1; i <= n; i ++) {
        f >> v[i].x >> v[i].y >> v[i].d;
        if(mn.x > v[i].x) mn = v[i];
        else if(mn.x == v[i].x && mn.y > v[i].y) mn.y = v[i].y;
    }
    for(int i = 1; i <= n; i ++) {
        v[i].x -= mn.x;
        v[i].y -= mn.y;
    }

    for(int i = 1; i <= n; i ++) {
        v[i].tg = atan2(v[i].y, v[i].x);
    }
    sort(v + 2, v + n + 1, cmp);

    v[0] = v[n];
    v[n + 1] = v[1];
    double dx = v[0].x - v[2].x;
    double dy = v[0].y - v[2].y;
    double aux = (double) ( sqrt((double)(dx * dx + dy * dy)) )* v[1].d / 2;

    dp[1][1] = aux; luat[1][1] = true;
    for(int i = 2; i < n; i ++) {

        dx = v[i - 1].x - v[i + 1].x;
        dy = v[i - 1].y - v[i + 1].y;
        aux = (double) (( sqrt(dx * dx + dy * dy) )* v[i].d) / 2;

        dp[i][1] = dp[i - 1][0]; luat[i][1] = luat[i - 1][0];
        for(int j = i - 2; j > 0; j --) {
            if(dp[i][1] < dp[j][0]) dp[i][1] = dp[j][0], luat[i][1] = luat[j][0];
            else if(dp[i][1] == dp[j][0]) luat[i][1] &= luat[j][0];
            if(dp[i][1] < dp[j][1]) dp[i][1] = dp[j][1], luat[i][1] = luat[j][1];
            else if(dp[i][1] == dp[j][1]) luat[i][1] &= luat[j][1];
        }
        dp[i][1] += aux;

        luat[i][0] = true;
        for(int j = i - 1; j > 0; j --) {
            if(dp[i][0] < dp[j][1]) dp[i][0] = dp[j][1], luat[i][0] = luat[j][1];
            else if(dp[i][0] == dp[j][1]) luat[i][0] &= luat[j][1];
            if(dp[i][0] < dp[j][0]) dp[i][0] = dp[j][0], luat[i][0] = luat[j][0];
            else if(dp[i][0] == dp[j][0]) luat[i][0] &= luat[j][0];
        }
    }

    dx = v[n - 1].x - v[n + 1].x;
    dy = v[n - 1].y - v[n + 1].y;
    aux = (double) (( sqrt(dx * dx + dy * dy) )* v[n].d) / 2;

    int i = n;
    if(!luat[i - 1][0])
        dp[i][1] = dp[i - 1][0];
    for(int j = i - 2; j > 1; j --) {
        if(!luat[j][0] && dp[i][1] < dp[j][0])
            dp[i][1] = dp[j][0];

        if(!luat[j][1] && dp[i][1] < dp[j][1])
            dp[i][1] = dp[j][1];
    }
    dp[i][1] += aux;

    luat[i][0] = true;
    for(int j = i - 1; j > 0; j --) {
        if(dp[i][0] < dp[j][1]) dp[i][0] = dp[j][1], luat[i][0] = luat[j][1];
        else if(dp[i][0] == dp[j][1]) luat[i][0] &= luat[j][1];
        if(dp[i][0] < dp[j][0]) dp[i][0] = dp[j][0], luat[i][0] = luat[j][0];
        else if(dp[i][0] == dp[j][0]) luat[i][0] &= luat[j][0];
    }

    double s = 0;
    for(int i = 1; i <= n; i ++) {
        s = max(s, dp[i][0]);
        s = max(s, dp[i][1]);
    }
    fprintf(g, "%.6f\n", s);
    return 0;
}