POJ 3334 - Connected Gheeves

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

概要

Gheeves とは，以下の条件を満たす点列 (p[1], ..., p[n]) を直線で結んでできる漏斗のような形をしたものである． 図があるのでイメージしやすい．

x 座標がすべて負の gheeves P と，x 座標がすべて正の gheeves Q が与えられる． この2つの gheeves は，太さの無視できる管で底が繋がっている．

これに容量 A の水を入れたときの，水位の y 座標を答える． 今は二次元上で考えているので，面積が容量に等しい．

ただし，もし水位がいずれかの gheeves のへりより高くなった場合，そこから水はこぼれ落ちる．

制約

上の gheeves の定義にある通り

制約

水位 h に関して，そのときの容量を計算して二分探索．

線分 pq に対して，pq が h より低ければ台形，pq と h が交わっていれば三角形を足していくことで容量を求める．

 1 #include <cstdio>
 2 #include <vector>
 3 #include <complex>
 4 using namespace std;
 5 typedef complex<double> P;
 6 static const double EPS = 1e-6;
 7 
 8 inline double cross(const P& a, const P& b) { return a.real()*b.imag() - b.real()*a.imag(); }
 9 
10 struct line
11 {
12   P a, b;
13   line() {}
14   line(const P& p, const P& q) : a(p), b(q) {}
15 };
16 
17 struct segment
18 {
19   P a, b;
20   segment() {}
21   segment(const P& x, const P& y) : a(x), b(y) {}
22 
23   inline bool intersects(const line& ln) const
24   {
25     return cross(ln.b - ln.a, a - ln.a) * cross(ln.b - ln.a, b - ln.a) < EPS;
26   }
27 
28   inline P intersection(const line& ln) const
29   {
30     const P x = b - a;
31     const P y = ln.b - ln.a;
32     return a + x*(cross(y, ln.a - a))/cross(y, x);
33   }
34 };
35 
36 double area(const vector<segment> *ps, double h)
37 {
38   double s = 0.0;
39   const line ln(P(0, h), P(1, h));
40   for (int i = 0; i < 2; i++) {
41     for (vector<segment>::const_iterator it = ps[i].begin(); it != ps[i].end(); ++it) {
42       P a = it->a, b = it->b;
43       if (a.imag() < b.imag()) {
44         swap(a, b);
45       }
46 
47       if (a.imag() <= h) {
48         s += (h - a.imag() + h - b.imag()) * fabs(a.real() - b.real()) / 2.0;
49       } else if (it->intersects(ln)) {
50         const P p = it->intersection(ln);
51         s += fabs(p.real() - b.real()) * (p.imag() - b.imag()) / 2.0;
52       }
53     }
54   }
55   return s;
56 }
57 
58 int main()
59 {
60   int T;
61   scanf("%d", &T);
62   while (T-- > 0) {
63     int A;
64     scanf("%d", &A);
65     vector<segment> ps[2];
66     double left = 1e10;
67     for (int i = 0; i < 2; i++) {
68       int k;
69       scanf("%d", &k);
70       P prev;
71       for (int j = 0; j < k; j++) {
72         int x, y;
73         scanf("%d %d", &x, &y);
74         left = min(left, double(y));
75         if (j != 0) {
76           ps[i].push_back(segment(prev, P(x, y)));
77         }
78         prev = P(x, y);
79       }
80     }
81     double right = min(min(ps[0].front().a.imag(), ps[0].back().b.imag()), min(ps[1].front().a.imag(), ps[1].back().b.imag()));
82     for (int i = 0; i < 100; i++) {
83       const double mid = (left + right)/2.0;
84       const double s = area(ps, mid);
85       if (s < A) {
86         left = mid;
87       } else {
88         right = mid;
89       }
90     }
91     printf("%.3f\n", (left + right)/2.0);
92   }
93   return 0;
94 }
poj/3334.cc