ACM-ICPC 2018 北京网络赛:K-Dimensional Foil II

#1835 : K-Dimensional Foil II

时间限制:1000ms

单点时限:1000ms

内存限制:256MB

描述

"K-Dimensional Foil" is a dimensional weapon. Its function is quite easy: It can ascend a region in 3D space to K (K≥3) dimension. One can use it to give the enemy unexpected attack. It was called "The Ultimate Weapon".

--"Remembrance of Mars's Past"

You are the chief technology officer in the space fleet, and your fleet was just suffered from the attack of the K-Dimensional Foil. The good news was that you have found the key parameter K, the dimension of the space. But staying in high dimensional space is very dangerous, you must destroy the K-Dimensional Foil as fast as possible.

You have n spaceships, spaceship i locates at s_i = (s_i,1, …, s_i,K), and the K-Dimensional Foil is a 1-norm ball with center c = (c₁, …, c_K) and radius r, a 1-norm ball with center c and radius r is a point set defined as
{x | d(x, c) ≤ r}, d(x, c) =∑| x_i - c_i |

In the formula above, the coordinate of point x is (x₁, x₂ … x_K)

Your spaceships will fire laser cannon to destroy the K-Dimensional Foil. The energy decay is very quick with the increase of the distance in the high dimensional space, so for every spaceship, you want to find the closest point (in Euclidean distance) on the K-Dimensional Foil. It's guaranteed that no spaceship is in the K-Dimensional Foil initially.

输入

The first line of the input is an integer T (T ≤ 100), the number of the test cases.

For each test case, the first line contains two integer n, K (1 ≤ n ≤ 50, 1 ≤ K ≤ 100), the number of spaceship in your fleet and the dimension of the space.

Then one line contains an integer r (1 ≤ r ≤ 10⁴ ), the radius of the K-Dimensional Foil.

Then one line contains K integers c₁, … c_K, meaning the coordinate of the center of the K-Dimensional Foil.

Then n lines follow. Each line contains K integers s_i,1, …, s_i,K, meaning the coordinate of a spaceship.

All the absolute values of the coordinate are smaller than 10⁴.

输出

For each test case, output n lines. The i^th line contains K numbers representing the coordinate of the closest point on the K-Dimensional Foil to the i^th spaceship. The absolute error between your output and the answer should be less than 10^-4

提示

The K-Dimensional Foil in the sample was a square with vertex: (1,0), (0,1), (-1,0), (0,-1)

This problem is special judged.

样例输入

样例输出

0.50 0.50
0.00 1.00

题目大意：忽略曼哈顿面的中心，平移所有顶点后，简化为数学语言便是已知

Σ|ai|== R

求使

Σ(yi-ai)²

的值最小的ai数组。

从二维思考到高维度，假设坐标 yi 全部大于0，当这种情况出现时，最近的点一定在第一象限，也就是 ai >= 0。

则设 L(a) = (Σ|ai| - R)

当yi全部满足 yi>=0时，假设ai>=0

则 L(a) = λ*(Σai - R)

则 F(a) = Σ(yi-ai)² + L(a)

对于每一个ai求偏导数，最后化简得到

λ = 2（Σyi - R）/n

ai = yi - λ

当得到ai < 0时与假设不符，调整ai为0，继续重复操作直到所有ai均不小于0

最后调整符号为对应“象限”。

#include <bits/stdc++.h>
#define P(n, f) cout<<n<<(f?'
':' ')
#define pi pair<int,int>
#define LL long long
#define ULL unsigned long long
#define lowbit(x) x&(-x)
#define mp make_pair
#define elif else if
#define range(i, a, b) for(auto i=a;i<=b;++i)
#define itrange(i, a, b) for(auto i=a;i!=b;++i)
#define rerange(i, a, b) for(auto i=a;i>=b;--i)
#define fill(arr, tmp) memset(arr,tmp,sizeof(arr))
#define IOS ios::sync_with_stdio(false), cin.tie(0)
using namespace std;
vector<string>ret;
vector<string>::iterator END;
bool cmp(const string &a,const string &b){
    return a.size()!=b.size() ?a.size() > b.size():a<b;
}
bool can[105];
double a[105];
void deal(vector<pair<int,int > >&y,int R) {
    memset(can, -1, sizeof(can));
    bool flag;
    int cur = y.size();
    int cnt = 0;
    do {
        flag = false;
        int res = 0;
        for (int i = 0; i < y.size(); ++i) {
            if (can[i])res += y[i].first;///绝对值
        }
        double lambda = 1.0 * (res - R) / cur;
        for(int i = 0 ; i < y.size() ; ++i){
            if(can[i]){
                a[i] = y[i].first - lambda;
                if(a[i] < 0){
                    can[i] = false;
                    a[i] = 0;
                    flag = true;
                    --cur;
                }
            }
        }
    }while (flag);
    for(int i = 0 ; i < y.size() ; ++i){
        a[i]*=y[i].second;///符号
    }
}


vector<pair<int,int> >Data;
int ORI[105];
int n,x,y,k,tmp;
int FUN(int a){
    if(a)return abs(a)/a;
    else return 1;
}
void init() {
    int T,R;
    cin>>T;
    while (T--) {
        cin>>n>>k>>R;
        range(i, 1, k) {
            scanf("%d",ORI+i-1);
        }
        range(i, 1, n) {
            Data.clear();
            range(j, 1, k) {
                scanf("%d",&tmp);
                Data.emplace_back(make_pair(abs(tmp - ORI[j - 1]), FUN(tmp - ORI[j - 1])));
            }
            deal(Data, R);
            for(int ___ = 0 ; ___ < k ; ++___){
                printf("%.5lf",a[___]+ORI[___]);
                if(___!=k-1)printf(" ");
                else puts("");
            }
        }
    }
}

void solve() {

}

int main() {
    init();
    solve();
    return 0;
}

嗯，目标函数时平方函数 yi ai同号才是最小值。

然后就变成一道水题了？

（纪念没加原点坐标吃下的罚时）