Cod sursa(job #1789404)

Utilizator maria15Maria Dinca maria15 Data 26 octombrie 2016 22:46:53
Problema A+B Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.79 kb
#include <fstream>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <iomanip>
#define INF 10010

using namespace std;

struct stalp {
    int x;
    int y;
    int d;
    double s;
};

void swap(stalp &a, stalp &b) {  // interschimb valorile
    stalp aux = a;
    a = b;
    b = aux;
}

int det(const stalp &a, const stalp &b) {  // calculez aria triunghiului format de cei doi stalpi cu originea
    return a.x * b.y - a.y * b.x;
}

int cmp (const stalp &a, const stalp &b) {
    // in caz de egalitate dupa unghi, sortez dupa distanta fata de origine
    if (a.x * b.y - a.y * b.x == 0) {
        return a.x * a.x + a.y * a.y > b.x * b.x + b.y * b.y;
    }
    return a.x * b.y - a.y * b.x > 0;
}

double dist(stalp a, stalp b) {    // distanta dintre doi stalpi
    double r = sqrt(1.0*(a.x-b.x) * (a.x-b.x) + (a.y-b.y) * (a.y-b.y));
    return r;
}

stalp v[1003], aux;
int n, xmin, ymin, p;
double maxim, D[1003];
int main () {
    ifstream fin ("mosia.in");
    ofstream fout("mosia.out");
    fin>>n;
    ymin = INF;
    xmin = INF;
    for (int i = 1; i<=n; i++) {
        fin>>v[i].x>>v[i].y>>v[i].d;
        if ((v[i].y < ymin) || ( (v[i].y == ymin) && (v[i].x < xmin)  )) {   //gasim punctul cel mai de jos si, dintre punctele
            ymin = v[i].y;                                                  //de pe ultimul nivel, pe cel mai din stanga = noua origine
            xmin = v[i].x;
            p = i;
        }
    }
    for (int i=1;i<=n;i++)
        v[i].x -= xmin, v[i].y -= ymin; // recalculam coordonatele stalpilor fata de noua origine
    swap(v[1], v[p]); // fixez primul element din vector ca fiind originea

    sort(v+2, v+n+1, cmp); // ??? le sorteaza dupa conditia de la cmp (daca cmp returneaza 1,
    int i;                // interchimba pe b cu a; daca nu, raman in ac ordine)

    // identific secventa de elemente de la inceput care sunt coliniare intre ele si cu originea
    for (i=2;i<n;i++) {
        if (det(v[i], v[i+1]) != 0)
            break;
    }
    // oglindesc aceasta secventa
    if (i!=2) {
        int j=2;
        while (j<i) {
            aux = v[j];
            v[j] = v[i];
            v[i] = aux;
            j++;
            i--;
        }
    }

    v[0] = v[n];
    v[n+1] = v[1];

    for (int i=1;i<=n;i++)
        v[i].s = v[i].d * dist(v[i-1], v[i+1]);

    maxim = D[n-2];

    for (int t = 1; t <= 2; t++) {
        D[1] = v[1].s;
        for (int i=2;i<=n-1;i++) {
            D[i] = D[i-1];
            if (D[i] < D[i-2] + v[i].s)
                D[i] = D[i-2] + v[i].s;
        }
        if (D[n-1] > maxim)
            maxim = D[n-1];

        for (int i=1;i<n;i++)
            v[i] = v[i+1];
    }

    fout<<setprecision(6)<<fixed<<maxim/2;
    return 0;
}