uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1058
半平面交求面积最值。直接枚举C(20,8)的所有情况即可。
代码如下：
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector> using namespace std; const int N = ;
struct Point {
double x, y;
Point() {}
Point(double x, double y) : x(x), y(y) {}
} pt[N], poly[N];
template<class T> T sqr(T x) { return x * x;} typedef Point Vec;
Vec operator + (Vec a, Vec b) { return Vec(a.x + b.x, a.y + b.y);}
Vec operator - (Vec a, Vec b) { return Vec(a.x - b.x, a.y - b.y);}
Vec operator * (Vec a, double p) { return Vec(a.x * p, a.y * p);}
Vec operator / (Vec a, double p) { return Vec(a.x / p, a.y / p);}
const double EPS = 1e-;
inline int sgn(double x) { return (x > EPS) - (x < -EPS);} inline double dotDet(Vec a, Vec b) { return a.x * b.x + a.y * b.y;}
inline double crossDet(Vec a, Vec b) { return a.x * b.y - a.y * b.x;}
inline double dotDet(Point o, Point a, Point b) { return dotDet(a - o, b - o);}
inline double crossDet(Point o, Point a, Point b) { return crossDet(a - o, b - o);}
inline double vecLen(Vec x) { return sqrt(dotDet(x, x));}
inline Vec normal(Vec x) { return Vec(-x.y, x.x) / vecLen(x);} struct DLine {
Point p;
Vec v;
double ang;
DLine() {}
DLine(Point p, Vec v) : p(p), v(v) { ang = atan2(v.y, v.x);}
bool operator < (const DLine &L) const { return ang < L.ang;}
DLine move(double x) { return DLine(p + normal(v) * x, v);}
} dl[N]; inline bool onLeft(DLine L, Point p) { return crossDet(L.v, p - L.p) > ;}
inline Point dLineIntersect(DLine a, DLine b) { return a.p + a.v * (crossDet(b.v, a.p - b.p) / crossDet(a.v, b.v));} struct Poly {
vector<Point> pt;
Poly() { pt.clear();}
~Poly() {}
Poly(vector<Point> &pt) : pt(pt) {}
Point operator [] (int x) const { return pt[x];}
int size() { return pt.size();}
double area() {
if (pt.size() < ) return 0.0;
double ret = 0.0;
for (int i = , sz = pt.size(); i < sz; i++)
ret += crossDet(pt[i], pt[(i + ) % sz]);
return fabs(ret / 2.0);
}
} ; Point p[N];
DLine q[N];
int halfPlane(DLine *L, int n) {
sort(L, L + n);
int fi, la;
q[fi = la = ] = L[];
for (int i = ; i < n; i++) {
while (fi < la && !onLeft(L[i], p[la - ])) la--;
while (fi < la && !onLeft(L[i], p[fi])) fi++;
q[++la] = L[i];
if (fabs(crossDet(q[la].v, q[la - ].v)) < EPS) {
la--;
if (onLeft(q[la], L[i].p)) q[la] = L[i];
}
if (fi < la) p[la - ] = dLineIntersect(q[la - ], q[la]);
}
while (fi < la && !onLeft(q[fi], p[la - ])) la--;
if (la < fi) return ;
p[la] = dLineIntersect(q[la], q[fi]);
int ret = ;
for (int i = fi; i <= la; i++) poly[ret++] = p[i];
return ret;
} //Poly halfPlane(DLine *L, int n) {
// Poly ret = Poly();
// sort(L, L + n);
// int fi, la;
// Point *p = new Point[n];
// DLine *q = new DLine[n];
// q[fi = la = 0] = L[0];
// for (int i = 1; i < n; i++) {
// while (fi < la && !onLeft(L[i], p[la - 1])) la--;
// while (fi < la && !onLeft(L[i], p[fi])) fi++;
// q[++la] = L[i];
// if (fabs(crossDet(q[la].v, q[la - 1].v)) < EPS) {
// la--;
// if (onLeft(q[la], L[i].p)) q[la] = L[i];
// }
// if (fi < la) p[la - 1] = dLineIntersect(q[la - 1], q[la]);
// }
// while (fi < la && !onLeft(q[fi], p[la - 1])) la--;
// if (la < fi) return ret;
// p[la] = dLineIntersect(q[la], q[fi]);
// for (int i = fi; i <= la; i++) ret.pt.push_back(p[i]);
// return ret;
//} double polyArea(Point *p, int n) {
if (n < ) return 0.0;
double sum = 0.0;
p[n] = p[];
Point O = Point(0.0, 0.0);
for (int i = ; i < n; i++) sum += crossDet(O, p[i], p[i + ]);
return fabs(sum / 2.0);
} double work(int st, int n, double d) {
// cout << st << endl;
for (int i = ; i < n; i++) dl[i] = DLine(pt[i], pt[i + ] - pt[i]).move((st & ( << i)) == ? 0.0 : d);
int tmp = halfPlane(dl, n);
return polyArea(poly, tmp);
// Poly tmp = halfPlane(dl, n);
// return tmp.area();
} int cntBit(int x) {
int cnt = ;
while (x > ) {
if (x & ) cnt++;
x >>= ;
}
return cnt;
} int main() {
// freopen("in", "r", stdin);
int n, k;
double d;
while (~scanf("%d%d%lf", &n, &k, &d) && (n + k + d > EPS)) {
for (int i = ; i < n; i++) scanf("%lf%lf", &pt[i].x, &pt[i].y);
pt[n] = pt[];
double ans = 0.0, area = polyArea(pt, n);
for (int i = , end = << n; i < end; i++) {
if (cntBit(i) <= k) {
// cout << i << endl;
ans = max(ans, area - work(i, n, d));
}
if (sgn(ans - area) == ) break;
}
printf("%.2f\n", ans);
}
return ;
}
能通过POJ的代码：
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector> using namespace std; const int N = ;
struct Point {
double x, y;
Point() {}
Point(double x, double y) : x(x), y(y) {}
} pt[N], poly[N];
template<class T> T sqr(T x) { return x * x;} typedef Point Vec;
Vec operator + (Vec a, Vec b) { return Vec(a.x + b.x, a.y + b.y);}
Vec operator - (Vec a, Vec b) { return Vec(a.x - b.x, a.y - b.y);}
Vec operator * (Vec a, double p) { return Vec(a.x * p, a.y * p);}
Vec operator / (Vec a, double p) { return Vec(a.x / p, a.y / p);}
const double EPS = 1e-;
inline int sgn(double x) { return (x > EPS) - (x < -EPS);} inline double dotDet(Vec a, Vec b) { return a.x * b.x + a.y * b.y;}
inline double crossDet(Vec a, Vec b) { return a.x * b.y - a.y * b.x;}
inline double dotDet(Point o, Point a, Point b) { return dotDet(a - o, b - o);}
inline double crossDet(Point o, Point a, Point b) { return crossDet(a - o, b - o);}
inline double vecLen(Vec x) { return sqrt(dotDet(x, x));}
inline Vec normal(Vec x) { return Vec(-x.y, x.x) / vecLen(x);} struct DLine {
Point p;
Vec v;
double ang;
DLine() {}
DLine(Point p, Vec v) : p(p), v(v) { ang = atan2(v.y, v.x);}
bool operator < (const DLine &L) const { return ang < L.ang;}
DLine move(double x) { return DLine(p + normal(v) * x, v);}
} dl[N]; inline bool onLeft(DLine L, Point p) { return crossDet(L.v, p - L.p) > ;}
inline Point dLineIntersect(DLine a, DLine b) { return a.p + a.v * (crossDet(b.v, a.p - b.p) / crossDet(a.v, b.v));} struct Poly {
vector<Point> pt;
Poly() { pt.clear();}
~Poly() {}
Poly(vector<Point> &pt) : pt(pt) {}
Point operator [] (int x) const { return pt[x];}
int size() { return pt.size();}
double area() {
if (pt.size() < ) return 0.0;
double ret = 0.0;
for (int i = , sz = pt.size(); i < sz; i++)
ret += crossDet(pt[i], pt[(i + ) % sz]);
return fabs(ret / 2.0);
}
} ; Point p[N];
DLine q[N], tmpDL[N];
int halfPlane(DLine *L, int n) {
for (int i = ; i < n; i++) tmpDL[i] = L[i];
sort(L, L + n);
int fi, la;
q[fi = la = ] = L[];
for (int i = ; i < n; i++) {
while (fi < la && !onLeft(L[i], p[la - ])) la--;
while (fi < la && !onLeft(L[i], p[fi])) fi++;
q[++la] = L[i];
if (fabs(crossDet(q[la].v, q[la - ].v)) < EPS) {
la--;
if (onLeft(q[la], L[i].p)) q[la] = L[i];
}
if (fi < la) p[la - ] = dLineIntersect(q[la - ], q[la]);
}
for (int i = ; i < n; i++) L[i] = tmpDL[i];
while (fi < la && !onLeft(q[fi], p[la - ])) la--;
if (la < fi) return ;
p[la] = dLineIntersect(q[la], q[fi]);
int ret = ;
for (int i = fi; i <= la; i++) poly[ret++] = p[i];
return ret;
} double polyArea(Point *p, int n) {
if (n < ) return 0.0;
double sum = 0.0;
p[n] = p[];
Point O = Point(0.0, 0.0);
for (int i = ; i < n; i++) sum += crossDet(O, p[i], p[i + ]);
return fabs(sum / 2.0);
} double work(int st, int n, double d) {
// cout << st << endl;
for (int i = ; i < n; i++) dl[i] = DLine(pt[i], pt[i + ] - pt[i]).move((st & ( << i)) == ? 0.0 : d);
int tmp = halfPlane(dl, n);
return polyArea(poly, tmp);
// Poly tmp = halfPlane(dl, n);
// return tmp.area();
} int cntBit(int x) {
int cnt = ;
while (x > ) {
if (x & ) cnt++;
x >>= ;
}
return cnt;
} const double FINF = 1e100;
double ans, d;
void dfs(int id, int tt, int used, int k) {
if (id >= tt) {
int tmp = halfPlane(dl, tt);
ans = min(ans, polyArea(poly, tmp));
return ;
}
dl[id] = DLine(pt[id], pt[id + ] - pt[id]);
dfs(id + , tt, used, k);
if (used >= k) return ;
dl[id] = DLine(pt[id], pt[id + ] - pt[id]).move(d);
dfs(id + , tt, used + , k);
} int main() {
// freopen("in", "r", stdin);
int n, k;
while (~scanf("%d%d%lf", &n, &k, &d) && (n + k + d > EPS)) {
for (int i = ; i < n; i++) scanf("%lf%lf", &pt[i].x, &pt[i].y);
pt[n] = pt[];
double area = polyArea(pt, n);
ans = FINF;
dfs(, n, , k);
printf("%.2f\n", area - ans);
}
return ;
}
——written by Lyon