2711: [Violet 2]After 17
Time Limit: 5 Sec Memory Limit: 128 MB
Submit: 224 Solved: 153Description
Input
Output
Sample Input
4
4 5
1 2
3 3
4 1Sample Output
-38.00HINT
Source
【分析】
虽然是道水题，但是我今天终于自己真正想出来一道了，撒花~~还挤到第7啦~~
点积的话，就是求$x2*x1+x3*x1+x3*x2+...+xn*x(n-1)+y2*y1+y3*y1+y3*y2+...yn*y(n-1)$
设$sumx=x1+x2+...+xn, sumy=y1+y2+...yn$
就是$sumx^2-\sum xi^2+sumy^2-\sum yi^2$
$x$和$y$没有半毛钱关系，分开做。
其实是很显然$(x,y)$是只会选择那角落四个点的【这是套路也是可以证(luan)明(shuo)的，【就是假设把一个$x$增加$a$ 贡献是$2a(x-sumx)$,你总往好的一边增加就好了。
那么$xi^2+yi^2$也是固定的。
那么就要$sumx$和$sumy$尽量接近0就好了。
这个，很熟悉吧？把$\dfrac{\sum xi}{2}$当成背包容量，把背包尽量填满就行了，这个0-1背包bool就好。
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define Maxn 210
#define LL long long bool f[Maxn*Maxn];
int nx[Maxn],ny[Maxn]; int main()
{
int n,ans=,h1=,h2=;
scanf("%d",&n);
for(int i=;i<=n;i++)
{
int x,y;
scanf("%d%d",&x,&y);
ans-=x*x+y*y;
h1+=x;h2+=y;
nx[i]=x;ny[i]=y;
}
memset(f,,sizeof(f));
f[]=;
for(int i=;i<=n;i++)
{
for(int j=h1/;j>=nx[i];j--)
{
f[j]|=f[j-nx[i]];
}
}
int mx=;
for(int i=;i<=h1/;i++) if(f[i]) mx=i;
ans+=(h1-*mx)*(h1-*mx);
memset(f,,sizeof(f));
f[]=;
for(int i=;i<=n;i++)
{
for(int j=h2/;j>=ny[i];j--)
{
f[j]|=f[j-ny[i]];
}
}
mx=;
for(int i=;i<=h2/;i++) if(f[i]) mx=i;
ans+=(h2-*mx)*(h2-*mx);
printf("%.2lf\n",ans*1.0/);
return ;
}
2017-04-06 16:45:10