首页 > 代码库 > HDU 5964 平行四边形

HDU 5964 平行四边形

假设直线L和L‘相交于原点O。假设S ={s1,s2,...,sn}是平面上的n个点。你打 算找四个点满足如下条件:
1.   A  L 而 A‘  L‘。
2.   B,B‘都属于S;即 BS 且B‘S。
3.   A,A‘的中点与B,B‘的中点重叠。这意味着ABA‘B‘是一个平行四边形(或者退 化的平行四边形)。
4.  平行四边形ABA‘B‘的面积最大。

 

(中文题目,好评!)

 

题解来源:ICPCCamp

技术分享

 

吐槽:

现场只有一组数据的,OJ上改成了多组。而且是超级多组

导致了卡输入。

 

没用快速读入的时候T,用了只跑了300ms

 

代码如下:

 1 //快速读入的板子就不贴啦!
 2 LL a, b, c, d;
 3 LL t1, t2, t3;
 4 LL f(LL x, LL y)
 5 {
 6     return t1 * x * x + t2 * y * y + t3 * x * y;
 7 }
 8 int main()
 9 {
10     LL n;
11     while (get_LL(a) == 1)
12     {
13         get_LL(b);
14         get_LL(c);
15         get_LL(d);
16         get_LL(n);
17         t1 = a * c;
18         t2 = b * d;
19         t3 = a * d + b * c;
20         LL minF = LINF, maxF = -LINF;
21         LL x, y;
22         for (int i = 0; i < n; i++)
23         {
24             get_LL(x);
25             get_LL(y);
26             LL v = f(x, y);
27             minF = min(minF, v);
28             maxF = max(maxF, v);
29         }
30         printf("%.f\n", fabs(double(maxF - minF) / (a * d - b * c)));
31     }
32     return 0;
33 }

 

HDU 5964 平行四边形