Pagini recente » Cod sursa (job #880099) | Cod sursa (job #1031136) | Cod sursa (job #2689346) | Cod sursa (job #588183) | Cod sursa (job #1789404)
#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;
}