打重现赛时,一点思路也没有,然后又看到这题AC数那么少,就直接放弃了。今天重新看了看,借鉴了下别人的,发现此题应该算是一道可解题。
看上去,这题的ans是同时有两个点作为自变量的函数(然而n^2复杂度显然不对,这也应该早点想到)。其实,这道题可以先直接假设S中的两个点的坐标分别为B(x1,y1),B'(x2,y2),然后,利用高中学到的解析几何的知识,得到中点坐标的表达式,再结合两条直线的方程,得到A,A'的坐标表达式,有平行四边形四个顶点的坐标,面积也就可以求得了。以上过程全部在纸上完成。最后可以发现,B和B'的坐标完全是分开的2333,不会产生某种“莫名的耦合”来一起影响ans,具体的公式可以见代码。
所以,以后看到这样的题,不管结果怎样,先动手算一下,有时在草稿纸上暴力笔算就能得到公式了。
题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=5964
#include<bits/stdc++.h> using namespace std; typedef long long LL; LL a1,a2,b1,b2; LL fun(LL x,LL y) { return a1*a2*x*x+b1*b2*y*y+(a1*b2+a2*b1)*x*y; } int main() { while(~scanf("%lld%lld%lld%lld",&a1,&b1,&a2,&b2)) { LL n; LL s1=-(<<),s2=<<; scanf("%lld",&n); while(n--) { LL x,y; scanf("%lld%lld",&x,&y); LL s=fun(x,y); s1=max(s1,s); s2=min(s2,s); } printf("%.0lf\n",fabs((double)(s1-s2)/(double)(a1*b2-b1*a2))); } }