唉 被秀了。。。 还是太弱，说好的数形结合呢，列个式子出来后就被吓到了，然后就懵逼了。
题意：
有一条狗，从原点出发，沿n个向量走，每个向量只走一次，沿着一个向量（x,y）走时，既可以往(x,y)方向走，也可以往(-x,-y)方向走。 然后问这条狗离原点最远的距离。
如果写成方程:
n个向量分别表示为： (x1,y1) (x2,y2) (x3,y3) ... (xn,yn)
第i个向量往(xi,yi)方向则ai=1,否则ai=-1
则ans = (a1*x1+a2*x2+...+an*xn)^2 + (a1*y1+a2*y2+...+an*yn)^2
要你给出一个(a1,a2,...,an)使得ans最大。
我以为写出方程形式会有助于做题，然并卵。。。
这题还是要用直观的方法理解。。。
数形结合方法：
定理1：如果把一个向量的正方向和反方向都算上，那么最优解的n个向量必然在一个半平面内。
证明： 假设最优解中的n个向量不在一个半平面内，一定可以找到一个直线l，使得直线左右两边都存在向量，那么将直线l左边的向量都转变为其反向量，那么结果一定大于最优解。
定理2: 如果把一个向量的正方向和反方向都算上，并以对x正半轴夹角排序，则连续的n个向量必两两不同（即不会存在一个向量的正向量和反向量都存在的情况）。
证： 显然。
由这两个定理，那么这题就很好做了，把所有的(xi,yi)(-xi,-yi)都算上，然后进行极角排序，枚举连续的n个记录最大值即可。
#include <iostream> #include <stdio.h> #include <string.h> #include <math.h> #include <algorithm> using namespace std; #define N 110 const double PI = acos(-1.0);// PI struct node { int x,y; double ang; }g[2*N]; double GetAngle(double x,double y) { double tmp=atan2(y,x); if(tmp<0) tmp=2*PI+tmp; return tmp; } double dis(int x,int y) { return sqrt((double)x*x+(double)y*y); } int cmp(node t1,node t2) { return t1.ang<t2.ang; } //泥煤,完全想错了。。。 int main(int argc, const char * argv[]) { int n; while(scanf("%d",&n) && n) { int cnt=0; for(int i=0;i<n;i++) { int x,y; scanf("%d%d",&x,&y); g[cnt].x=x; g[cnt].y=y; g[cnt].ang=GetAngle(x, y); cnt++; g[cnt].x=-x; g[cnt].y=-y; g[cnt].ang=GetAngle(-x, -y); cnt++; } sort(g,g+cnt,cmp); int pi,pj; pi=0; double ans=0; for(;pi<cnt;pi++) { int x=0,y=0; pj=pi; for(int j=0;j<n;j++) { x+=g[pj].x; y+=g[pj].y; pj=(pj+1)%cnt; } ans=max(ans,dis(x,y)); } /* ans*=10000; int tmp=((long long)ans)%10; ans/=10; if(tmp>5) ans++; ans/=1000; char strans[110]; sprintf(strans,"%lf",ans); for(int i=0;i<100;i++) { if(strans[i] == '.') { printf("%c",strans[i]); for(int j=0;j<3;j++) { printf("%c",strans[i+1+j]); } break; } else printf("%c",strans[i]); } printf(" "); */ printf("%.3lf ",ans); } return 0; }
PS:最后题目中说的四舍五入是扯淡，直接%.3lf即可。