This Takes the Cake 恶心的面积剖分 不过是水题
#include <iostream>#include <cmath>using namespace std;struct point{ double x, y;};double a1, a2, d, s;double area(int n, point* p){ double s1=0, s2=0; for(int i=0; i<n; i++) s1 += p[(i+1)%n].y*p[i].x, s2 += p[(i+1)%n].y*p[(i+2)%n].x; return fabs(s1-s2)/2;}void check(double s1){ double s2 = s - s1; double ds = fabs(s1 - s2); if(ds < d) { if(s1 > s2) swap(s1, s2); d = ds, a1 = s1, a2 = s2; }}void solve(point *p){ point p1[4], p2[4]; int i; for(i=0; i<4; i++) p1[i].x = (p[i].x+p[(i+1)%4].x)/2, p1[i].y = (p[i].y+p[(i+1)%4].y)/2; for(i=0; i<4; i++) { p2[0] = p[i], p2[1] = p[(i+1)%4], p2[2] = p[(i+2)%4]; check(area(3, p2)); p2[2].x = (p[(i+1)%4].x+p[(i+2)%4].x)/2, p2[2].y = (p[(i+1)%4].y+p[(i+2)%4].y)/2; check(area(3, p2)); p2[2] = p[(i+3)%4], p2[1].x = (p[(i+2)%4].x+p[(i+3)%4].x)/2, p2[1].y = (p[(i+2)%4].y+p[(i+3)%4].y)/2; check(area(3, p2)); p2[1] = p[i+1], p2[2] = p1[i+1], p2[3] = p1[(i+3)%4]; check(area(4, p2)); p2[0] = p1[i], p2[1] = p[(i+1)%4], p2[2] = p1[(i+1)%4]; check(area(3, p2)); }}int main(){ point p[4]; int i, j=0; while(1) { d = 1000000; for(i=0; i<4; i++) cin >> p[i].x >> p[i].y; if(!p[0].x && !p[0].y && !p[1].x && !p[1].y) break; s = area(4, p); solve(p); printf("Cake %d: %.3lf %.3lf\n", ++j, a1, a2); }}
