首页 > 代码库 > HDU_5964:平行四边形
HDU_5964:平行四边形
打重现赛时,一点思路也没有,然后又看到这题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
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long LL; 4 5 LL a1,a2,b1,b2; 6 7 LL fun(LL x,LL y) 8 { 9 return a1*a2*x*x+b1*b2*y*y+(a1*b2+a2*b1)*x*y; 10 } 11 12 int main() 13 { 14 15 while(~scanf("%lld%lld%lld%lld",&a1,&b1,&a2,&b2)) 16 { 17 LL n; 18 LL s1=-(1<<30),s2=1<<30; 19 scanf("%lld",&n); 20 while(n--) 21 { 22 LL x,y; 23 scanf("%lld%lld",&x,&y); 24 LL s=fun(x,y); 25 s1=max(s1,s); 26 s2=min(s2,s); 27 } 28 printf("%.0lf\n",fabs((double)(s1-s2)/(double)(a1*b2-b1*a2))); 29 } 30 }
HDU_5964:平行四边形
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。