POJ 1408 - Fishnet

http://poj.org/problem?id=1408

概要

(0,0), (1,0), (0,1), (1,1) からなる正方形の領域がある． n 個の要素からなる数列 a[i], b[i], c[i], d[i] が与えられる．

(a[i],0) と (b[i],1) を直線で結び，(0,c[i]) と (1,d[i]) を直線で結ぶと，正方形の領域の中に (n+1)^2 個の領域ができる． これらの領域の中で，最も大きな面積を答える．

制約

• n < n <= 30
• 0 < a[i], b[i], c[i], d[i] < 1
• 答えは 10^-6 の精度で出力

解法

(n+1)^2 個すべての領域の面積を実際に求めて最大値をとるだけ．

 1 #include <cstdio>
 2 #include <vector>
 3 #include <complex>
 4 using namespace std;
 5 typedef complex<double> P;
 6 
 7 inline double cross(const P& a, const P& b)
 8 {
 9   return a.real()*b.imag() - b.real()*a.imag();
10 }
11 
12 struct segment
13 {
14   P a, b;
15   segment() {}
16   segment(const P& x, const P& y) : a(x), b(y) {}
17   inline double distance(const P& p) const
18   {
19     return abs(cross(p - a, b - a)) / abs(b - a);
20   }
21   inline P intersect(const segment& seg) const
22   {
23     const double d1 = seg.distance(a);
24     const double d2 = seg.distance(b);
25     const double t = d1 / (d1 + d2);
26     return (1-t)*a + t*b;
27   }
28 };
29 ostream& operator<<(ostream& os, const segment& seg)
30 {
31   return os << seg.a << "-" << seg.b;
32 }
33 
34 double area(const vector<P>& poly)
35 {
36   double a = 0.0;
37   const int N = poly.size();
38   for (int i = 0; i < N; i++) {
39     a += cross(poly[i], poly[(i+1)%N]);
40   }
41   return abs(a)/2.0;
42 }
43 
44 int main()
45 {
46   int N;
47   while (scanf("%d", &N) != EOF && N != 0) {
48     vector<double> ps[4];
49     for (int i = 0; i < 4; i++) {
50       ps[i].push_back(0.0);
51       for (int j = 0; j < N; j++) {
52         double x;
53         scanf("%lf", &x);
54         ps[i].push_back(x);
55       }
56       ps[i].push_back(1.0);
57     }
58 
59     double ans = 0.0;
60     for (int i = 0; i <= N; i++) {
61       for (int j = 0; j <= N; j++) {
62         const P a1(ps[0][i], 0.0), a2(ps[0][i+1], 0.0);
63         const P b1(ps[1][i], 1.0), b2(ps[1][i+1], 1.0);
64         const P c1(0.0, ps[2][j]), c2(0.0, ps[2][j+1]);
65         const P d1(1.0, ps[3][j]), d2(1.0, ps[3][j+1]);
66         const segment left(a1, b1), right(a2, b2);
67         const segment bottom(c1, d1), top(c2, d2);
68         vector<P> poly;
69         poly.push_back(left.intersect(top));
70         poly.push_back(right.intersect(top));
71         poly.push_back(right.intersect(bottom));
72         poly.push_back(left.intersect(bottom));
73         ans = max(ans, area(poly));
74       }
75     }
76     printf("%.6f\n", ans);
77   }
78   return 0;
79 }