首页 > 代码库 > zoj 1806 This Takes the Cake 计算凸四边形和三角形的面积

zoj 1806 This Takes the Cake 计算凸四边形和三角形的面积

2024-07-03 12:44:21   224人阅读

题目来源：

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=806

题意：

凸四边形上 有8个点， 4个顶点 ， 和 每2个顶点的中点。经过这8个点的每一条线段，将四边形分成2份， 求这两份面积最近的面积。 

分析：  枚举， 每条线段， 计算 一边面积 S(较小)， 另一边 面积 s1 = sum - S  ,   找使 S / S1 最大的 面积， 即可。

代码如下：

double add(double a, double b){
    return (fabs(a+b) < EPS * (fabs(a) + fabs(b))) ? 0 : (a + b) ;
}
struct Point{
    double x, y  ;
    Point(){}
    Point(double x, double y):x(x),y(y){}
    Point operator - (Point p){
        return Point(add(x, -p.x) , add(y, -p.y)) ;
    }
    double operator ^(Point p){
        return add(x * p.y , - y * p.x) ;
    }
    void putout(){
        printf("%lf :%lf \n", x ,  y) ;
    }
} po[30];
double area(int s, int e){
   double sum = 0.0 ;
    for(int i = s ; i < e ; i++){
            sum += (po[i]^po[(i+1)] )* 0.5 ;
        }
        sum += (po[e]^po[s])*0.5 ;
    return sum = sum  >  0 ?  sum : - sum;
}
int main()
{
    int i , j, g = 1 ;
    double sum  , Max , res;
    while(1){
        for(i = 0 ;  i < 7 ; i += 2){
            scanf("%lf%lf", &po[i].x, &po[i].y) ;
        }
        if(!(po[0].x || po[0].y
        || po[2].x || po[2].y
        || po[4].x || po[4].y
        || po[6].x || po[6].y))
         break;
        Max = 0 ;
        res = 0.0 ;
        for(i = 1 ; i < 8 ; i+= 2){
            po[i].x =  (po[i-1].x + po[(i+1)%8].x ) * 0.5;
            po[i].y =  (po[i-1].y + po[(i+1)%8].y ) * 0.5;
        }
        sum =  area(0 , 7);
        for(i = 0 ; i < 8 ; i++){
            for(j = i+1 ; j < 8 ; j++){
                double S = area(i , j) ;
                double S1 = sum - S ;
                if(S > S1)
                    swap(S ,S1);
                if(S / S1 > Max)
                {
                    Max =  S / S1 ;
                    res = S ;
                }
            }
        }
        printf("Cake %d: %.3lf %.3lf\n" , g++ ,res , sum - res) ;

    }
}

 


联系
我们