LA 2402 (枚举) Fishnet

浏览数：34 / 时间：2015年06月09日

题意：

正方形四个边界上分别有n个点，将其划分为(n+1)²个四边形，求四边形面积的最大值。

分析：

因为n的规模很小，所以可以二重循环枚举求最大值。

求直线(a, 0) (b, 0) 和直线(0, c) (0, d)的交点，我是二元方程组求解得来的，然后再用叉积求面积即可。

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <cmath>
 4 #include <algorithm>
 5 
 6 const int maxn = 30 + 10;
 7 struct HEHE
 8 {
 9     double a, b, c, d;
10 }hehe[maxn];
11 
12 struct Point
13 {
14     double x, y;
15     Point(double x=0, double y=0):x(x), y(y) {}
16 };
17 typedef Point Vector;
18 
19 Vector operator - (const Vector& A, const Vector& B)
20 { return Vector(A.x - B.x, A.y - B.y); }
21 
22 double Cross(const Vector& A, const Vector& B)
23 { return (A.x*B.y - A.y*B.x); }
24 
25 Point GetIntersection(const double& a, const double& b, const double& c, const double& d)
26 {
27     double x = (a+(b-a)*c) / (1-(b-a)*(d-c));
28     double y = (d-c)*x+c;
29     return Point(x, y);
30 }
31 
32 int main(void)
33 {
34     //freopen("2402in.txt", "r", stdin);
35     
36     int n;
37     while(scanf("%d", &n) == 1 && n)
38     {
39         memset(hehe, 0, sizeof(hehe));
40         for(int i = 1; i <= n; ++i) scanf("%lf", &hehe[i].a);
41         for(int i = 1; i <= n; ++i) scanf("%lf", &hehe[i].b);
42         for(int i = 1; i <= n; ++i) scanf("%lf", &hehe[i].c);
43         for(int i = 1; i <= n; ++i) scanf("%lf", &hehe[i].d);
44         hehe[n+1].a = hehe[n+1].b = hehe[n+1].c = hehe[n+1].d = 1.0;
45         
46         double ans = 0.0;
47         for(int i = 0; i <= n; ++i)
48             for(int j = 0; j <= n; ++j)
49             {
50                 Point A, B, C, D;
51                 A = GetIntersection(hehe[i].a, hehe[i].b, hehe[j].c, hehe[j].d);
52                 B = GetIntersection(hehe[i+1].a, hehe[i+1].b, hehe[j].c, hehe[j].d);
53                 C = GetIntersection(hehe[i+1].a, hehe[i+1].b, hehe[j+1].c, hehe[j+1].d);
54                 D = GetIntersection(hehe[i].a, hehe[i].b, hehe[j+1].c, hehe[j+1].d);
55                 double temp = 0.0;
56                 temp += Cross(B-A, C-A) / 2;
57                 temp += Cross(C-A, D-A) / 2;
58                 ans = std::max(ans, temp);
59             }
60             
61         printf("%.6f\n", ans);
62     }
63     
64     return 0;
65 }