# Requirements

## 题目描述

An undergraduate student, realizing that he needs to do research to improve his chances of being accepted to graduate school, decided that it is now time to do some independent research. Of course, he has decided to do research in the most important domain: the requirements he must fulfill to graduate from his undergraduate university. First, he discovered (to his surprise) that he has to fulfill $5$ distinct requirements: the general institute requirement, the writing requirement, the science requirement, the foreign-language requirement, and the field-of-specialization requirement. Formally, a requirement is a fixed number of classes that he has to take during his undergraduate years. Thus, for example, the foreign language requirement specifies that the student has to take $4$ classes to fulfill this requirement: French I, French II, French III, and French IV. Having analyzed the immense multitude of the classes that need to be taken to fulfill the different requirements, our student became a little depressed about his undergraduate university: there are so many classes to take…
Dejected, the student began studying the requirements of other universities that he might have chosen after high school. He found that, in fact, other universities had exactly the same $5$ requirements as his own university. The only difference was that different universities had different number of classes to be satisfied in each of the five requirement.
Still, it appeared that universities have pretty similar requirements (all of them require a lot of classes), so he hypothesized that no two universities are very dissimilar in their requirements. He defined the dissimilarity of two universities $X$ and $Y$ as $\sum_{i=1}^5 |x_i-y_i|$, where an $x_i$($y_i$) is the number of classes in the requirement $i$ of university $X$($Y$) multiplied by an appropriate factor that measures hardness of the corresponding requirement at the corresponding university.

## 算法分析

\begin{align} (x_1+y_1)&-(x_2+y_2) \\ (x_1-y_1)&-(x_2-y_2) \\ (-x_1+y_1)&-(-x_2+y_2) \\ (-x_1-y_1)&-(-x_2-y_2) \end{align}

## 代码

#include <cstdio>
#include <algorithm>

using std :: min;
using std :: max;

static const int N = 100000;
double a[N][5];

int main() {
int n;
while (~ scanf("%d", &n)) {
for (int i = 0; i < n; ++ i)
for (int j = 0; j < 5; ++ j) scanf("%lf", &a[i][j]);
double ans = 0;
for (int i = 0; i < 32; ++ i) {
double mx = -1e100, mn = 1e100;
for (int j = 0; j < n; ++ j) {
double rec = 0;
for (int k = 0; k < 5; ++ k)
if (i & 1 << k) rec += a[j][k]; else rec -= a[j][k];
mx = max(mx, rec), mn = min(mn, rec);
}
ans = max(ans, mx - mn);
}
printf("%.2lf\n", ans);
}
return 0;
}


418 I'm a teapot