簡單計算幾何，我的做法是列出所有可能的切法（一共18種），求最優(yōu)值。
/**//*************************************************************************
Author: WHU_GCC
Created Time: 2007-9-26 17:48:45
File Name: pku1624.cpp
Description:
************************************************************************/
// 平面計算幾何
// Author: Felicia @ GCC
// Last Modified: 2007.09.17
#include <iostream>
#include <cmath>
using namespace std;
typedef long long int64;
const int maxint = 0x7FFFFFFF;
const int64 maxint64 = 0x7FFFFFFFFFFFFFFFLL;
const double eps = 1E-9;
const double pi = acos(-1.0);
const double inf = 1E200;
#define out(x) (cout<<#x<<": "<<x<<endl)
template <class T> void show(T a, int n) 
{for (int i = 0; i < n; ++i) cout << a[i] << ' '; cout << endl;}
template <class T> void show(T a, int r, int l) {for (int i = 0; i < r; ++i) show(a[i],l); cout << endl;}
/**//********************
基本幾何結(jié)構(gòu)
點
線段
直線
多邊形
圓
********************/
// 點, 同時也可以看成向量
struct point_t
{
double x, y;
point_t(double a = 0, double b = 0)
{
x = a;
y = b;
}
};
// 線段
struct lineseg_t
{
point_t s, e;
lineseg_t()
{
}
lineseg_t(point_t a, point_t b)
{
s = a;
e = b;
}
};
// 直線
// 解析方程 ax + by + c = 0 為統(tǒng)一表示，約定 a >= 0
struct line_t
{
double a, b, c;
line_t(double d1 = 1, double d2 = -1, double d3 = 0)
{
a = d1;
b = d2;
c = d3;
}
};
// 這里定義多邊形的最大點數(shù)
const int max_polygon_size = 1000;
// 多邊形, 規(guī)定逆時針為正方向
struct polygon_t
{
int n;
point_t p[max_polygon_size];
};
// 圓
struct circle_t
{
point_t center;
double r;
};
/**//********************
常用小函數(shù)與算符
浮點數(shù)比較
平方
點到原點距離
兩點距離
兩點重合
********************/
// 浮點數(shù)與0比較. x == 0 返回 0, x > 0 返回 1, x < 0 返回 -1
int dcmp(double x)
{
if (-eps < x && x < eps)
return 0;
else if (x > 0)
return 1;
else
return -1;
}
// 判斷兩個點是否重合
bool operator ==(const point_t &a, const point_t &b)
{
return dcmp(a.x - b.x) == 0 && dcmp(a.y - b.y) == 0;
}
bool operator !=(const point_t &a, const point_t &b)
{
return !(a == b);
}
// 向量加法
point_t operator +(const point_t &a, const point_t &b)
{
point_t ret(a.x + b.x, a.y + b.y);
return ret;
}
// 向量減法
point_t operator -(const point_t &a, const point_t &b)
{
point_t ret(a.x - b.x, a.y - b.y);
return ret;
}
// 平方
inline double sqr(double x)
{
return x * x;
}
// 點到原點距離
double dist(const point_t &p)
{
return sqrt(sqr(p.x) + sqr(p.y));
}
// 兩點距離
double dist(const point_t &a, const point_t &b)
{
return sqrt(dist(a - b));
}
/**//********************\
* *
* 點的基本運算 *
* *
\********************/
/**//******************************************************************************
r=multiply(sp,ep,op),得到(sp-op)*(ep-op)的叉積
r>0:ep在矢量opsp的逆時針方向；
r=0：opspep三點共線；
r<0:ep在矢量opsp的順時針方向
*******************************************************************************/
double cross_mul(const point_t &a, const point_t &b)
{
return a.x * b.y - a.y * b.x;
}
double dot_mul(const point_t &a, const point_t &b)
{
return a.x * b.x + a.y * b.y;
}
double cross_mul(const point_t &a, const point_t &b, const point_t &c)
{
return cross_mul(a - c, b - c);
}
/**//*******************************************************************************
r=dotmultiply(p1,p2,op),得到矢量(p1-op)和(p2-op)的點積，如果兩個矢量都非零矢量
r<0:兩矢量夾角為銳角；r=0：兩矢量夾角為直角；r>0:兩矢量夾角為鈍角
*******************************************************************************/
double dot_mul(const point_t &a, const point_t &b, const point_t &c)
{
return dot_mul(a - c, b - c);
}
// 判斷點p是否在線段l上
// 條件：p在線段l所在的直線上 && 點p在以線段l為對角線的矩形內(nèi)
bool online(const lineseg_t l, const point_t p)
{
return dcmp(cross_mul(l.e, p, l.s)) == 0 && (p.x - l.s.x) * (p.x - l.e.x) <= 0 && (p.y - l.s.y) * (p.y - l.e.y) <= 0;
}
// 返回點p以點o為圓心逆時針旋轉(zhuǎn)alpha(單位：弧度)后所在的位置
point_t rotate(const point_t &o, double alpha, point_t p)
{
point_t ret;
p.x -= o.x;
p.y -= o.y;
ret.x = p.x * cos(alpha) - p.y * sin(alpha) + o.x;
ret.y = p.y * cos(alpha) + p.x * sin(alpha) + o.y;
return ret;
}
// 返回向量a按逆時針方向,旋轉(zhuǎn)到向量b的角度
// 角度小于pi，返回正值
// 角度大于pi，返回負(fù)值
double angle(const point_t &a, const point_t &b)
{
double ret = acos(dot_mul(a, b) / (dist(a) * dist(b)));
if (cross_mul(a, b) < 0)
return ret;
else
return -ret;
}
// 返回頂角在o點,起始邊為os,終止邊為oe的夾角(單位:弧度),規(guī)定逆時針為正方向
// 角度小于pi，返回正值
// 角度大于pi，返回負(fù)值
// 可以用于求線段之間的夾角
double angle(const point_t &o, const point_t &s, const point_t &e)
{
return angle(s - o, e - o);
}
// 線段及直線的基本運算
/**//* 判斷點與線段的關(guān)系,用途很廣泛
本函數(shù)是根據(jù)下面的公式寫的,P是點C到線段AB所在直線的垂足
AC dot AB
r = ---------
||AB||^2
(Cx-Ax)(Bx-Ax) + (Cy-Ay)(By-Ay)
= -------------------------------
L^2
r has the following meaning:
r=0 P = A
r=1 P = B
r<0 P is on the backward extension of AB
r>1 P is on the forward extension of AB
0<r<1 P is interior to AB
*/
double relation(const point_t &p, const lineseg_t &l)
{
return dot_mul(p, l.e, l.s) / (dist(l.s, l.e) * dist(l.s, l.e));
}
// 求點p到線段l所在直線的垂足
point_t foot(const point_t &p, const lineseg_t &l)
{
double r = relation(p, l);
point_t ret;
ret.x = l.s.x + r * (l.e.x - l.s.x);
ret.y = l.s.y + r * (l.e.y - l.s.y);
return ret;
}
// 求點p到線段l的最短距離,并返回線段上距該點最近的點ret
// 注意: ret是線段l上到點p最近的點,不一定是垂足
double dist(const point_t p, const lineseg_t &l, point_t &ret)
{
double r = relation(p,l);
if (r < 0)
ret = l.s;
else if (r > 1)
ret = l.e;
else
ret = foot(p,l);
return dist(p, ret);
}
// 求點p到線段l所在直線的距離,請注意本函數(shù)與上個函數(shù)的區(qū)別
double dist(const point_t p, const lineseg_t l)
{
return abs(cross_mul(p, l.e, l.s)) / dist(l.s, l.e);
}
// 計算點到折線集的最近距離,并返回最近點
double dist(int cnt_v, point_t point_set[], const point_t &p, point_t &ret_p)
{
double ret = inf;
for (int i = 0; i < cnt_v - 1; i++)
{
lineseg_t l(point_set[i], point_set[i + 1]);
point_t tmp_p;
double tmp = dist(p, l, tmp_p);
if (tmp < ret)
{
ret = tmp;
ret_p = tmp_p;
}
}
return ret;
}
// 判斷圓是否在多邊形內(nèi)
bool inside(const circle_t c, int cnt_v, point_t poly[])
{
point_t q;
double d = dist(cnt_v, poly, c.center, q);
return d < c.r || fabs(d - c.r) < eps;
}
// 如果線段a和b相交(包括相交在端點處)時返回true
bool intersect_e(const lineseg_t &a, const lineseg_t &b)
{
return
//排斥實驗
max(a.s.x, a.e.x) >= min(b.s.x, b.e.x) &&
max(b.s.x, b.e.x) >= min(a.s.x, a.e.x) &&
max(a.s.y, a.e.y) >= min(b.s.y, b.e.y) &&
max(b.s.y, b.e.y) >= min(a.s.y, a.e.y) &&
//跨立實驗
cross_mul(b.s, a.e, a.s) * cross_mul(a.e, b.e, a.s) >= 0 &&
cross_mul(a.s, b.e, b.s) * cross_mul(b.e, a.e, b.s) >= 0;
}
// 線段a和b相交 && 交點不是雙方的端點時返回true
bool intersect_ne(const lineseg_t &a, const lineseg_t &b)
{
return
intersect_e(a, b) &&
!online(a, b.s) &&
!online(a, b.e) &&
!online(b, a.e) &&
!online(b, a.s);
}
// 線段l所在直線與線段a相交(包括相交在端點處)時返回true
// 方法:判斷線段a是否跨立線段l
bool intersect_l(const lineseg_t &a, const lineseg_t &l)
{
return cross_mul(a.s, l.e, l.s) * cross_mul(l.e, a.e, l.s) >= 0;
}
// 根據(jù)已知兩點坐標(biāo),求過這兩點的直線解析方程: ax + by + c = 0 (a >= 0)
// 若兩點不重合,返回true,否則返回false
bool make_line(const point_t &a, const point_t &b, line_t &ret)
{
int sign = 1;
ret.a = b.y - a.y;
if (dcmp(ret.a) == 0 && dcmp(b.x - a.x) == 0)
return false;
if (dcmp(ret.a) == 0)
{
ret.a = 0;
ret.b = 1;
ret.c = -a.y;
return true;
}
if (ret.a < 0)
{
sign = -1;
ret.a = -ret.a;
}
ret.b = sign * (a.x - b.x);
ret.c = sign * (a.y * b.x - a.x * b.y);
return true;
}
// 根據(jù)直線解析方程返回直線的斜率k,水平線返回0,豎直線返回inf
double slope(const line_t &l)
{
if (dcmp(l.a) == 0)
return 0;
if (dcmp(l.b) == 0)
return inf;
return -(l.a / l.b);
}
// 返回直線的傾斜角alpha (0 - pi)
double alpha(const line_t &l)
{
if (dcmp(l.a) == 0)
return 0;
if (dcmp(l.b) == 0)
return pi / 2;
double k = slope(l);
return k > 0 ? atan(k) : pi + atan(k);
}
// 求點p關(guān)于直線l的對稱點
point_t symmetry(const line_t &l, const point_t &p)
{
point_t ret;
double sla = sqr(l.a), slb = sqr(l.b);
ret.x = ((slb - sla) * p.x - 2 * l.a * l.b * p.y - 2 * l.a * l.c) / (sla + slb);
ret.y = ((sla - slb) * p.y - 2 * l.a * l.b * p.x - 2 * l.b * l.c) / (sla + slb);
return ret;
}
// 如果兩條直線 l1(a1x + b1y + c1 = 0), l2(a2x + b2y + c2 = 0)相交, 返回true, 且返回交點p
bool intersect(const line_t &l1, const line_t &l2, point_t &p)
{
double d = l1.a * l2.b - l2.a * l1.b;
if (dcmp(d) == 0)
return false;
p.x = (l2.c * l1.b - l1.c * l2.b) / d;
p.y = (l2.a * l1.c - l1.a * l2.c) / d;
return true;
}
// 如果線段l1和l2相交，返回true且交點由(inter)返回，否則返回false
bool intersect(const lineseg_t &l1, const lineseg_t &l2, point_t &ret)
{
line_t t1, t2;
if (!make_line(l1.s, l1.e, t1))
return false;
if (!make_line(l2.s, l2.e, t2))
return false;
if (intersect(t1, t2, ret))
return online(l1, ret) && online(l2, ret);
else
return false;
}
//點到直線距離
double dist(const point_t &a, const line_t &b)
{
return abs(b.a * a.x + b.b * a.y + b.c) / sqrt(sqr(b.a) + sqr(b.b));
}
const int size[] =
{
3, 3, 3, 3, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3
};
const int poly[18][4] =
{
{0, 1, 7},
{1, 2, 3},
{3, 4, 5},
{5, 6, 7},
{1, 2, 4, 5},
{0, 2, 3, 7},
{0, 2, 3},
{0, 2, 4},
{0, 2, 5},
{2, 4, 5},
{2, 4, 6},
{2, 7, 0},
{4, 6, 7},
{4, 6, 0},
{4, 1, 2},
{6, 0, 1},
{6, 0, 2},
{6, 3, 4},
};
point_t p[8];
int main()
{
int t1, t2, t3, t4, t5, t6, t7, t8;
int ca = 1;
while (scanf("%d%d%d%d%d%d%d%d", &t1, &t2, &t3, &t4, &t5, &t6, &t7, &t8),
t1 != 0 || t2 != 0 || t3 != 0 || t4 != 0 || t5 != 0 || t6 != 0 || t7 != 0 || t8 != 0)
{
p[0].x = t1;
p[0].y = t2;
p[2].x = t3;
p[2].y = t4;
p[4].x = t5;
p[4].y = t6;
p[6].x = t7;
p[6].y = t8;
p[1].x = (p[0].x + p[2].x) / 2;
p[1].y = (p[0].y + p[2].y) / 2;
p[3].x = (p[2].x + p[4].x) / 2;
p[3].y = (p[2].y + p[4].y) / 2;
p[5].x = (p[4].x + p[6].x) / 2;
p[5].y = (p[4].y + p[6].y) / 2;
p[7].x = (p[6].x + p[0].x) / 2;
p[7].y = (p[6].y + p[0].y) / 2;
double area = cross_mul(p[0], p[2]) + cross_mul(p[2], p[4]) + cross_mul(p[4], p[6]) + cross_mul(p[6], p[0]);
double ans = 1e200, ans_a, ans_b;
for (int i = 0; i < 18; i++)
{
double tmp = 0;
for (int j = 0; j < size[i]; j++)
tmp += cross_mul(p[poly[i][j]], p[poly[i][(j + 1) % size[i]]]);
if (fabs(area - tmp - tmp) < ans)
{
ans = fabs(area - tmp - tmp);
ans_a = tmp;
ans_b = area - tmp;
}
}
if (ans_a > ans_b)
swap(ans_a, ans_b);
printf("Cake %d: %.3lf %.3lf\n", ca++, ans_a / 2, ans_b / 2);
}
return 0;
}