比赛 20120925 评测结果 AAAAAAAAAA
题目名称 油滴扩展 最终得分 100
用户昵称 王者自由 运行时间 0.005 s
代码语言 C++ 内存使用 1.69 MiB
提交时间 2012-09-25 19:56:48
显示代码纯文本
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
using namespace std;
#define sqr(u) ((u)*(u))
const int N = 10;
const double pi = 3.1415926;
int n, a, b, c, d;
int x[N], y[N], l[N];
double u, s, t, r[N], w[N][N];
double zheng(double u) {
    return u > 0 ? u : 0;
}
int main() {
    freopen("oilbox.in", "r", stdin);
    freopen("oilbox.out", "w", stdout);
    scanf("%d", &n);
    scanf("%d %d %d %d", &a, &b, &c, &d);
    for(int i=1; i<=n; i++) {
        scanf("%d %d", x+i, y+i);
        l[i] = i;
        w[0][i] = min(abs(a - x[i]), abs(c - x[i]));
        w[i][0] = min(abs(b - y[i]), abs(d - y[i]));
        w[0][i] = min(w[0][i], w[i][0]);
    }
    for(int i=1; i<=n; i++)
        for(int j=1; j<i; j++)
            w[i][j] = w[j][i] = sqrt((double) sqr(x[i] - x[j]) + sqr(y[i] - y[j]));
    s = u = abs(c - a) * abs(d - b);
    do {
        t = u;
        for(int i=1; i<=n; i++) {
            r[l[i]] = w[0][l[i]];
            for(int j=1; j<i; j++)
                r[l[i]] = min(r[l[i]], zheng(w[l[i]][l[j]] - r[l[j]]));
            t -= pi * sqr(r[l[i]]);
        }
        s = min(s, t);
    } while(next_permutation(l+1, l+n+1));
    printf("%.0lf\n", s);
    return 0;
}