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