假设直线L和L'相交于原点O。假设S ={s1,s2,...,sn}是平面上的n个点。你打 算找四个点满足如下条件:
1. A ∈ L 而 A' ∈ L'。
2. B,B'都属于S;即 B∈S 且B'∈S。
3. A,A'的中点与B,B'的中点重叠。这意味着ABA'B'是一个平行四边形(或者退 化的平行四边形)。
4. 平行四边形ABA'B'的面积最大。
(中文题目,好评!)
题解来源:ICPCCamp
吐槽:
现场只有一组数据的,OJ上改成了多组。而且是超级多组
导致了卡输入。
没用快速读入的时候T,用了只跑了300ms
代码如下:
//快速读入的板子就不贴啦!
LL a, b, c, d;
LL t1, t2, t3;
LL f(LL x, LL y)
{
return t1 * x * x + t2 * y * y + t3 * x * y;
}
int main()
{
LL n;
while (get_LL(a) == )
{
get_LL(b);
get_LL(c);
get_LL(d);
get_LL(n);
t1 = a * c;
t2 = b * d;
t3 = a * d + b * c;
LL minF = LINF, maxF = -LINF;
LL x, y;
for (int i = ; i < n; i++)
{
get_LL(x);
get_LL(y);
LL v = f(x, y);
minF = min(minF, v);
maxF = max(maxF, v);
}
printf("%.f\n", fabs(double(maxF - minF) / (a * d - b * c)));
}
return ;
}
HDU 5964 平行四边形的更多相关文章
-
hdu 5964:平行四边形 【计算几何】
打重现赛时,一点思路也没有,然后又看到这题AC数那么少,就直接放弃了.今天重新看了看,借鉴了下别人的,发现此题应该算是一道可解题. 看上去,这题的ans是同时有两个点作为自变量的函数(然而n^2复杂度 ...
-
hdu_5964:平行四边形
打重现赛时,一点思路也没有,然后又看到这题AC数那么少,就直接放弃了.今天重新看了看,借鉴了下别人的,发现此题应该算是一道可解题. 看上去,这题的ans是同时有两个点作为自变量的函数(然而n^2复杂度 ...
-
2018 HDU多校第三场赛后补题
2018 HDU多校第三场赛后补题 从易到难来写吧,其中题意有些直接摘了Claris的,数据范围是就不标了. 如果需要可以去hdu题库里找.题号是6319 - 6331. L. Visual Cube ...
-
HDU - 3506 Monkey Party
HDU - 3506 思路: 平行四边形不等式优化dp 这不就是石子归并(雾 代码: #pragma GCC optimize(2) #pragma GCC optimize(3) #pragma G ...
-
HDOJ 2111. Saving HDU 贪心 结构体排序
Saving HDU Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total ...
-
【HDU 3037】Saving Beans Lucas定理模板
http://acm.hdu.edu.cn/showproblem.php?pid=3037 Lucas定理模板. 现在才写,noip滚粗前兆QAQ #include<cstdio> #i ...
-
hdu 4859 海岸线 Bestcoder Round 1
http://acm.hdu.edu.cn/showproblem.php?pid=4859 题目大意: 在一个矩形周围都是海,这个矩形中有陆地,深海和浅海.浅海是可以填成陆地的. 求最多有多少条方格 ...
-
HDU 4569 Special equations(取模)
Special equations Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u S ...
-
HDU 4006The kth great number(K大数 +小顶堆)
The kth great number Time Limit:1000MS Memory Limit:65768KB 64bit IO Format:%I64d & %I64 ...
随机推荐
-
Java并发基础总结
并发是一种能并行运行多个程序或并行运行一个程序中多个部分的能力.如果程序中一个耗时的任务能以异步或并行的方式运行,那么整个程序的吞吐量和可 交互性将大大改善.现代的PC都有多个CPU或一个CPU中有多 ...
-
vbscript调用WMI一键式式发布网站
作为.net开发,在window环境下,不得不熟悉些脚本语言,来减轻些日常开发中所遇到的一些繁杂的事情,比如自动发布网站,自动发布网站等等. WMI windows管理程序接口,可用各种与语言调用,方 ...
-
在Chrome Console中加载jQuery
var jq = document.createElement('script'); jq.src = "//ajax.googleapis.com/ajax/libs/jquery/1/j ...
-
Flask-SQLALchemy查询
from: http://blog.sina.com.cn/s/blog_633277f90100kpvm.html 似乎ORM最难设计的部分是查询.特别是面向对象的查询,今天学习SQLAlchemy ...
-
javascript 延时执行函数
延时执行函数,貌似有些多此一举, 也许还是有点用 记在这儿 var test = { delay : function(lifetime){ var data; setTimeout(function ...
-
Tennis Championship
Tennis Championship time limit per test 2 seconds memory limit per test 256 megabytes input standard ...
-
HTML5结构标签
<!DOCTYPE html> <!-- ↑ 文档声明.HTML5已经简化为上述样式! 注意:文档声明必须有!而且必须在文档页面的第一行! HTML4.01之前的文档声明: &l ...
-
Docker:使用Jenkins构建Docker镜像
Docker 彭东稳 1年前 (2016-12-27) 10709次浏览 已收录 0个评论 一.介绍Jenkins Jenkins是一个开源项目,提供了一种易于使用的持续集成系统,使开发者从 ...
-
Linux系统中的文件权限
r(read) 4 可读 w(write) 2 可写 x() 1 可执行 644 755 rw-r-r ...
-
数学与猜想 合情推理模式 (G. 波利亚 著)
第十二章 几个著名模式 (已看) $1. 证实一个结论 $2. 连续证实几个结论 $3. 证实一个未必可信的结论 $4. 类比推理 $5. 加深类比 $6. 被隐没的类比推理 第十三章 更多的模式与最 ...