Pagini recente » Cod sursa (job #2597440) | Cod sursa (job #2567583) | Istoria paginii utilizator/igroita | Cod sursa (job #2587845) | Cod sursa (job #1589818)
#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;
}