poj 1271 && uva 10117 Nice Milk （半平面交）

uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1058

　　半平面交求面积最值。直接枚举C(20,8)的所有情况即可。

代码如下：

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <iostream>
  4 #include <algorithm>
  5 #include <cmath>
  6 #include <vector>
  7 
  8 using namespace std;
  9 
 10 const int N = 22;
 11 struct Point {
 12     double x, y;
 13     Point() {}
 14     Point(double x, double y) : x(x), y(y) {}
 15 } pt[N], poly[N];
 16 template<class T> T sqr(T x) { return x * x;}
 17 
 18 typedef Point Vec;
 19 Vec operator + (Vec a, Vec b) { return Vec(a.x + b.x, a.y + b.y);}
 20 Vec operator - (Vec a, Vec b) { return Vec(a.x - b.x, a.y - b.y);}
 21 Vec operator * (Vec a, double p) { return Vec(a.x * p, a.y * p);}
 22 Vec operator / (Vec a, double p) { return Vec(a.x / p, a.y / p);}
 23 const double EPS = 1e-8;
 24 inline int sgn(double x) { return (x > EPS) - (x < -EPS);}
 25 
 26 inline double dotDet(Vec a, Vec b) { return a.x * b.x + a.y * b.y;}
 27 inline double crossDet(Vec a, Vec b) { return a.x * b.y - a.y * b.x;}
 28 inline double dotDet(Point o, Point a, Point b) { return dotDet(a - o, b - o);}
 29 inline double crossDet(Point o, Point a, Point b) { return crossDet(a - o, b - o);}
 30 inline double vecLen(Vec x) { return sqrt(dotDet(x, x));}
 31 inline Vec normal(Vec x) { return Vec(-x.y, x.x) / vecLen(x);}
 32 
 33 struct DLine {
 34     Point p;
 35     Vec v;
 36     double ang;
 37     DLine() {}
 38     DLine(Point p, Vec v) : p(p), v(v) { ang = atan2(v.y, v.x);}
 39     bool operator < (const DLine &L) const { return ang < L.ang;}
 40     DLine move(double x) { return DLine(p + normal(v) * x, v);}
 41 } dl[N];
 42 
 43 inline bool onLeft(DLine L, Point p) { return crossDet(L.v, p - L.p) > 0;}
 44 inline Point dLineIntersect(DLine a, DLine b) { return a.p + a.v * (crossDet(b.v, a.p - b.p) / crossDet(a.v, b.v));}
 45 
 46 struct Poly {
 47     vector<Point> pt;
 48     Poly() { pt.clear();}
 49     ~Poly() {}
 50     Poly(vector<Point> &pt) : pt(pt) {}
 51     Point operator [] (int x) const { return pt[x];}
 52     int size() { return pt.size();}
 53     double area() {
 54         if (pt.size() < 3) return 0.0;
 55         double ret = 0.0;
 56         for (int i = 0, sz = pt.size(); i < sz; i++)
 57             ret += crossDet(pt[i], pt[(i + 1) % sz]);
 58         return fabs(ret / 2.0);
 59     }
 60 } ;
 61 
 62 Point p[N];
 63 DLine q[N];
 64 int halfPlane(DLine *L, int n) {
 65     sort(L, L + n);
 66     int fi, la;
 67     q[fi = la = 0] = L[0];
 68     for (int i = 1; i < n; i++) {
 69         while (fi < la && !onLeft(L[i], p[la - 1])) la--;
 70         while (fi < la && !onLeft(L[i], p[fi])) fi++;
 71         q[++la] = L[i];
 72         if (fabs(crossDet(q[la].v, q[la - 1].v)) < EPS) {
 73             la--;
 74             if (onLeft(q[la], L[i].p)) q[la] = L[i];
 75         }
 76         if (fi < la) p[la - 1] = dLineIntersect(q[la - 1], q[la]);
 77     }
 78     while (fi < la && !onLeft(q[fi], p[la - 1])) la--;
 79     if (la < fi) return 0;
 80     p[la] = dLineIntersect(q[la], q[fi]);
 81     int ret = 0;
 82     for (int i = fi; i <= la; i++) poly[ret++] = p[i];
 83     return ret;
 84 }
 85 
 86 //Poly halfPlane(DLine *L, int n) {
 87 //    Poly ret = Poly();
 88 //    sort(L, L + n);
 89 //    int fi, la;
 90 //    Point *p = new Point[n];
 91 //    DLine *q = new DLine[n];
 92 //    q[fi = la = 0] = L[0];
 93 //    for (int i = 1; i < n; i++) {
 94 //        while (fi < la && !onLeft(L[i], p[la - 1])) la--;
 95 //        while (fi < la && !onLeft(L[i], p[fi])) fi++;
 96 //        q[++la] = L[i];
 97 //        if (fabs(crossDet(q[la].v, q[la - 1].v)) < EPS) {
 98 //            la--;
 99 //            if (onLeft(q[la], L[i].p)) q[la] = L[i];
100 //        }
101 //        if (fi < la) p[la - 1] = dLineIntersect(q[la - 1], q[la]);
102 //    }
103 //    while (fi < la && !onLeft(q[fi], p[la - 1])) la--;
104 //    if (la < fi) return ret;
105 //    p[la] = dLineIntersect(q[la], q[fi]);
106 //    for (int i = fi; i <= la; i++) ret.pt.push_back(p[i]);
107 //    return ret;
108 //}
109 
110 double polyArea(Point *p, int n) {
111     if (n < 3) return 0.0;
112     double sum = 0.0;
113     p[n] = p[0];
114     Point O = Point(0.0, 0.0);
115     for (int i = 0; i < n; i++) sum += crossDet(O, p[i], p[i + 1]);
116     return fabs(sum / 2.0);
117 }
118 
119 double work(int st, int n, double d) {
120 //    cout << st << endl;
121     for (int i = 0; i < n; i++) dl[i] = DLine(pt[i], pt[i + 1] - pt[i]).move((st & (1 << i)) == 0 ? 0.0 : d);
122     int tmp = halfPlane(dl, n);
123     return polyArea(poly, tmp);
124 //    Poly tmp = halfPlane(dl, n);
125 //    return tmp.area();
126 }
127 
128 int cntBit(int x) {
129     int cnt = 0;
130     while (x > 0) {
131         if (x & 1) cnt++;
132         x >>= 1;
133     }
134     return cnt;
135 }
136 
137 int main() {
138 //    freopen("in", "r", stdin);
139     int n, k;
140     double d;
141     while (~scanf("%d%d%lf", &n, &k, &d) && (n + k + d > EPS)) {
142         for (int i = 0; i < n; i++) scanf("%lf%lf", &pt[i].x, &pt[i].y);
143         pt[n] = pt[0];
144         double ans = 0.0, area = polyArea(pt, n);
145         for (int i = 0, end = 1 << n; i < end; i++) {
146             if (cntBit(i) <= k) {
147 //                cout << i << endl;
148                 ans = max(ans, area - work(i, n, d));
149             }
150             if (sgn(ans - area) == 0) break;
151         }
152         printf("%.2f
", ans);
153     }
154     return 0;
155 }

View Code

能通过POJ的代码：

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <iostream>
  4 #include <algorithm>
  5 #include <cmath>
  6 #include <vector>
  7 
  8 using namespace std;
  9 
 10 const int N = 22;
 11 struct Point {
 12     double x, y;
 13     Point() {}
 14     Point(double x, double y) : x(x), y(y) {}
 15 } pt[N], poly[N];
 16 template<class T> T sqr(T x) { return x * x;}
 17 
 18 typedef Point Vec;
 19 Vec operator + (Vec a, Vec b) { return Vec(a.x + b.x, a.y + b.y);}
 20 Vec operator - (Vec a, Vec b) { return Vec(a.x - b.x, a.y - b.y);}
 21 Vec operator * (Vec a, double p) { return Vec(a.x * p, a.y * p);}
 22 Vec operator / (Vec a, double p) { return Vec(a.x / p, a.y / p);}
 23 const double EPS = 1e-8;
 24 inline int sgn(double x) { return (x > EPS) - (x < -EPS);}
 25 
 26 inline double dotDet(Vec a, Vec b) { return a.x * b.x + a.y * b.y;}
 27 inline double crossDet(Vec a, Vec b) { return a.x * b.y - a.y * b.x;}
 28 inline double dotDet(Point o, Point a, Point b) { return dotDet(a - o, b - o);}
 29 inline double crossDet(Point o, Point a, Point b) { return crossDet(a - o, b - o);}
 30 inline double vecLen(Vec x) { return sqrt(dotDet(x, x));}
 31 inline Vec normal(Vec x) { return Vec(-x.y, x.x) / vecLen(x);}
 32 
 33 struct DLine {
 34     Point p;
 35     Vec v;
 36     double ang;
 37     DLine() {}
 38     DLine(Point p, Vec v) : p(p), v(v) { ang = atan2(v.y, v.x);}
 39     bool operator < (const DLine &L) const { return ang < L.ang;}
 40     DLine move(double x) { return DLine(p + normal(v) * x, v);}
 41 } dl[N];
 42 
 43 inline bool onLeft(DLine L, Point p) { return crossDet(L.v, p - L.p) > 0;}
 44 inline Point dLineIntersect(DLine a, DLine b) { return a.p + a.v * (crossDet(b.v, a.p - b.p) / crossDet(a.v, b.v));}
 45 
 46 struct Poly {
 47     vector<Point> pt;
 48     Poly() { pt.clear();}
 49     ~Poly() {}
 50     Poly(vector<Point> &pt) : pt(pt) {}
 51     Point operator [] (int x) const { return pt[x];}
 52     int size() { return pt.size();}
 53     double area() {
 54         if (pt.size() < 3) return 0.0;
 55         double ret = 0.0;
 56         for (int i = 0, sz = pt.size(); i < sz; i++)
 57             ret += crossDet(pt[i], pt[(i + 1) % sz]);
 58         return fabs(ret / 2.0);
 59     }
 60 } ;
 61 
 62 Point p[N];
 63 DLine q[N], tmpDL[N];
 64 int halfPlane(DLine *L, int n) {
 65     for (int i = 0; i < n; i++) tmpDL[i] = L[i];
 66     sort(L, L + n);
 67     int fi, la;
 68     q[fi = la = 0] = L[0];
 69     for (int i = 1; i < n; i++) {
 70         while (fi < la && !onLeft(L[i], p[la - 1])) la--;
 71         while (fi < la && !onLeft(L[i], p[fi])) fi++;
 72         q[++la] = L[i];
 73         if (fabs(crossDet(q[la].v, q[la - 1].v)) < EPS) {
 74             la--;
 75             if (onLeft(q[la], L[i].p)) q[la] = L[i];
 76         }
 77         if (fi < la) p[la - 1] = dLineIntersect(q[la - 1], q[la]);
 78     }
 79     for (int i = 0; i < n; i++) L[i] = tmpDL[i];
 80     while (fi < la && !onLeft(q[fi], p[la - 1])) la--;
 81     if (la < fi) return 0;
 82     p[la] = dLineIntersect(q[la], q[fi]);
 83     int ret = 0;
 84     for (int i = fi; i <= la; i++) poly[ret++] = p[i];
 85     return ret;
 86 }
 87 
 88 double polyArea(Point *p, int n) {
 89     if (n < 3) return 0.0;
 90     double sum = 0.0;
 91     p[n] = p[0];
 92     Point O = Point(0.0, 0.0);
 93     for (int i = 0; i < n; i++) sum += crossDet(O, p[i], p[i + 1]);
 94     return fabs(sum / 2.0);
 95 }
 96 
 97 double work(int st, int n, double d) {
 98 //    cout << st << endl;
 99     for (int i = 0; i < n; i++) dl[i] = DLine(pt[i], pt[i + 1] - pt[i]).move((st & (1 << i)) == 0 ? 0.0 : d);
100     int tmp = halfPlane(dl, n);
101     return polyArea(poly, tmp);
102 //    Poly tmp = halfPlane(dl, n);
103 //    return tmp.area();
104 }
105 
106 int cntBit(int x) {
107     int cnt = 0;
108     while (x > 0) {
109         if (x & 1) cnt++;
110         x >>= 1;
111     }
112     return cnt;
113 }
114 
115 const double FINF = 1e100;
116 double ans, d;
117 void dfs(int id, int tt, int used, int k) {
118     if (id >= tt) {
119         int tmp = halfPlane(dl, tt);
120         ans = min(ans, polyArea(poly, tmp));
121         return ;
122     }
123     dl[id] = DLine(pt[id], pt[id + 1] - pt[id]);
124     dfs(id + 1, tt, used, k);
125     if (used >= k) return ;
126     dl[id] = DLine(pt[id], pt[id + 1] - pt[id]).move(d);
127     dfs(id + 1, tt, used + 1, k);
128 }
129 
130 int main() {
131 //    freopen("in", "r", stdin);
132     int n, k;
133     while (~scanf("%d%d%lf", &n, &k, &d) && (n + k + d > EPS)) {
134         for (int i = 0; i < n; i++) scanf("%lf%lf", &pt[i].x, &pt[i].y);
135         pt[n] = pt[0];
136         double area = polyArea(pt, n);
137         ans = FINF;
138         dfs(0, n, 0, k);
139         printf("%.2f
", area - ans);
140     }
141     return 0;
142 }

View Code

——written by Lyon