POJ 1271 - Nice Milk

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

概要

凸な n 角形のパンを高さ h のミルクに k 回までつけたとき，最大でどれくらいの面積をミルクにつけることができるかを答える．

制約

解法

全探索 + 多角形の切断．

ミルクをつける辺が同じならば順番は関係ないので，C(n,k) で全探索できる． 多角形の切断は n でできるため，全体で n * C(n,k) でだいたい 2.5 * 10^6 程度．

テストケースが最大10個で，浮動小数演算も多いので結構時間が厳しい． 実際 TLE を連発した． 最終的に vector を配列に変えることで通った… (297MS)

それと k <= n とは限らないことに注意． 最初これで RE を出した．

  1 #include <cstdio>
  2 #include <algorithm>
  3 #include <complex>
  4 using namespace std;
  5 typedef complex<double> P;
  6 static const double EPS = 1e-6;
  7 
  8 inline double dot(const P& a, const P& b)
  9 {
 10   return a.real()*b.real() + a.imag()*b.imag();
 11 }
 12 
 13 inline double cross(const P& a, const P& b)
 14 {
 15   return a.real()*b.imag() - b.real()*a.imag();
 16 }
 17 
 18 struct line
 19 {
 20   P base, dir;
 21   line() {}
 22   line(const P& x, const P& y) : base(x), dir(y - x) {}
 23 };
 24 
 25 struct segment
 26 {
 27   P a, b;
 28   segment() {}
 29   segment(const P& x, const P& y) : a(x), b(y) {}
 30 
 31   inline bool intersects(const line& ln) const
 32   {
 33     return cross(ln.dir, a - ln.base) * cross(ln.dir, b - ln.base) < EPS;
 34   }
 35 
 36   inline P intersection(const line& ln) const
 37   {
 38     const P x = b - a;
 39     return a + x*(cross(ln.dir, ln.base - a))/cross(ln.dir, x);
 40   }
 41 
 42   inline bool parallel(const line& ln) const
 43   {
 44     return abs(cross(ln.dir, b - a)) < EPS;
 45   }
 46 };
 47 
 48 struct polygon
 49 {
 50   int N;
 51   P ps[25];
 52   polygon() : N(0) {}
 53 
 54   inline int size() const { return N; }
 55   inline void push_back(const P& p) { ps[N++] = p; }
 56   inline P& operator[](int i) { return ps[i]; }
 57   inline const P& operator[](int i) const { return ps[i]; }
 58 
 59   double area() const
 60   {
 61     // positive if polygon is clockwise
 62     double a = 0.0;
 63     for (int i = 0; i < N; i++) {
 64       a += cross(ps[(i+1)%N], ps[i]);
 65     }
 66     return a/2.0;
 67   }
 68 
 69   polygon cut(const line& ln) const
 70   {
 71     // cut out the left-side of the line
 72     polygon ret;
 73     segment seg;
 74     for (int i = 0; i < N; i++) {
 75       seg.a = ps[i];
 76       seg.b = ps[(i+1)%N];
 77       if (cross(ln.dir, ps[i] - ln.base) < EPS) {
 78         // ps[i] is right-side of the line
 79         ret.push_back(ps[i]);
 80         if (!seg.parallel(ln) && seg.intersects(ln)) {
 81           const P p = seg.intersection(ln);
 82           if (abs(p - ps[i]) > EPS) {
 83             ret.push_back(p);
 84           }
 85         }
 86       } else if (!seg.parallel(ln) && seg.intersects(ln)) {
 87         ret.push_back(seg.intersection(ln));
 88       }
 89     }
 90     return ret;
 91   }
 92 };
 93 
 94 double dfs(const line *ls, int N, const polygon& poly, int i, int depth)
 95 {
 96   if (depth == 0) {
 97     return poly.area();
 98   } else {
 99     double ans = poly.area();
100     for (int j = i+1; j < N; j++) {
101       ans = min(ans, dfs(ls, N, poly.cut(ls[j]), j, depth-1));
102     }
103     return ans;
104   }
105 }
106 
107 int main()
108 {
109   int N, K, H;
110   while (scanf("%d %d %d", &N, &K, &H) != EOF && N != 0) {
111     K = min(K, N);
112     polygon poly;
113     for (int i = 0; i < N; i++) {
114       int x, y;
115       scanf("%d %d", &x, &y);
116       poly.push_back(P(x, y));
117     }
118     if (K == 0 || H == 0) {
119       puts("0.00");
120       continue;
121     }
122     reverse(poly.ps, poly.ps + N);
123 
124     static line ls[20];
125     for (int i = 0; i < N; i++) {
126       const P& p1 = poly[i];
127       const P& p2 = poly[(i+1)%N];
128       const P dir = p2 - p1;
129       const P n = dir*P(0.0, -1.0);
130       const P h = H/abs(n)*n + p1;
131       ls[i] = line(h, h + dir);
132     }
133     printf("%.2f\n", poly.area() - dfs(ls, N, poly, -1, K));
134   }
135   return 0;
136 }
poj/1271.cc