行车(a1*b1+a1*b2+..a1*bn+a2*b1+…an*bn=(a1+..an)(b1+..bn) )

行车
(bicycle.pas/cpp)
题目描述
骑在自行车上,让微风追逐着他衣角,在不经意间捕获着一颗颗芳心,骄阳似乎也没有此时的他耀眼,这便是机房的骄傲——建德!
这是每天都会发生在附中门口的一幕。而为了每天能够领略不同的风景,捕获更多的芳心,建德打算制定n 条线路。为了简化起见,我们把这个世界想象成一个平面直角坐标系,而建德所在的福建师大附中则为原点。由于建德不能绕的太进,他每次路线的目的地都被限制在一个对应的右上角为(x, y),左下角为(-x,-y)的矩形内。
每次建德都会从原点直接沿直线走到目的地。显然,他走过了一个向量,这被数学控的“毛毡”称为这次的路线向量。他为了更好地规划线路,为每条线路定义了一个无聊值,即这次的路线向量和其余所有乊前的线路的向量的点积和【对于向量(x1,y1),(x2,y2),他们的点积和即为x1x2+y1y2】。建德希望合理的选择目的地,使得所有线路的无聊值乊和最小。
输入格式
第一行一个正整数n ,表示建德打算制定n 条旅行线路。
接下来 n 行,每行两个整数x , y ,描述一个限制目的地的矩形。
输出格式
一行一个整数,即最小的无聊值,保留 2 位小数。
样例输入
2
1 2
2 1
样例输出
-4.00
数据范围与约定
对于10% 的数据,保证0<n<=5,0<x,y<=5。
对于 30% 的数据,保证0<n<=20,0<x,y<=100。
对于 100% 的数据,保证0<n<=200,0<x,y<=200。

首先 根据公式  n个数和m个数两两相乘的结果为n个数的和与m个数的和的积

而且x和y互不影响

于是套公式-两两相乘/2-交集   结果为 f(n)=  (x1+..+xn)^2+x1^2+..xn^2  )/2

易证  f(n)=(x1+…+xn-1)* xn   + f(n-1)

所以  xn 要么最大,要么最小 才能使 f(n)有最大/最小值

因为不知道 (x1+..x(n-1)的正负 所以只能靠猜( 既考虑最大,也考虑最小)

回到原公式 显然  要是 f(n)有最小值 就要另 (x1+..+xn)有最小值

于是就是分组背包各种做……

#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<cstring>
#include<cmath>
#include<functional>
#include<algorithm>
using namespace std;
#define MAXN (200+10)
#define MAXV ((40000+100)*2)
#define MAXX (200+10)
#define f(i,j)  f[ (i) ][ (j)+20000   ]
int n;
long long ans=0;
bool f[MAXN][MAXV];
int x[MAXN];
int y[MAXN];
int sqr(int x)
{
    return x*x;
}
int main()
{
    freopen("bicycle.in","r",stdin);
    freopen("bicycle.out","w",stdout);
    cin>>n;
    for (int i=1;i<=n;i++)
    {
        cin>>x[i]>>y[i];
        ans-=(long long)(sqr(x[i]))+sqr(y[i]);
    }
    memset(f,0,sizeof(f));
    f(0,0)=1;

    for (int i=1;i<=n;i++)
        for (int j=-i*200;j<=i*200;j++)
            f(i,j)=f(i-1,j-x[i])||f(i-1,j+x[i]);

    int j=0;

    while (!f(n,j)&&!f(n,-j)) j++;
    ans+=(long long)j*j;

//  cout<<j<<endl;

/*  int j=0;
    for (int i=0;i<=n;i++)
    {
        for (int j=-10;j<=10;j++)
            cout<<f(i,j);
        cout<<endl;
    }
*/
    memset(f,0,sizeof(f));
    f(0,0)=1;

    for (int i=1;i<=n;i++)
        for (int j=-i*200;j<=i*200;j++)
            f(i,j)=f(i-1,j-y[i])||f(i-1,j+y[i]);

    j=0;
    while (!f(n,j)&&!f(n,-j)) j++;

    ans+=(long long)j*j;

    cout.setf(ios::fixed);
    cout.precision(2);
    cout<<double(ans)/2<<endl;

//  while (1);

    return 0;
}