Tanky WooRSS

HDOJ 1071 The area

13 Jul 2010
这篇博客是从旧博客 WordPress 迁移过来,内容可能存在转换异常。

感觉此题不错,很标准的数学题。用到了高中的抛物线和直线,大学的高等数学中的积分知识。

概念不清楚的只能去查相关资料了。这里把大概讲一下:(注意:下面的关系式不是按标准的计算机表示方法书写的,所以诸如乘号*都省略了)

已知抛物线与直线相交两点和抛物线顶点,顶点P1(-2a/b, (4ac-b^2)/4a)。

抛物线方程:y = ax^2 + bx + c;

直线方程:y = kx+h;

已知p1, p2, p3可以求出a, b, c, k, h

然后是高数中的积分求面积了。(我高数不过关,不过这些基本还是记得的。=。=)

积分符号不太好打出来,这里直接给出积分后的面积公式了。

S = a/3 (x3^3 - x2 ^ 3) + (b-k)/2 * (x3^2 - x2^2) + (c-h)(x3-x2);

这里求出来a是关键,求出了a,则b,c,k,h都可以直接求出来了。

而a这里我半天没想到,看到网上写 a = (y2-y1)/((x2-x1)^2)

半天不懂,后来逆推才发现的。

y1 = ax1^2 + bx1 + c

y2 = ax2^2 + bx2 + c

y1- y2 = (x1- x2)(a(x1+x2) + b)

又x1 = -b/2a,

所以

y2- y1 = (x1-x2)^2

好吧,感觉讲的很仔细了。

再就是贴代码了:

// HDOJ 1071
// Author: Tanky Woo
 #include 
using namespace std;

typedef struct Co
{
    double x,y;
}Co;

Co p1, p2, p3;
// www.wutianqi.com
int main()
{
    //freopen("input.txt", "r", stdin);
    double a, b, c;   // 抛物线的参数
    double k, h;      // 直线的参数
    int nCases;
    scanf("%d", &nCases;);
    while(nCases--)
    {
        scanf("%lf %lf", &p1.x;, &p1.y;);
        scanf("%lf %lf", &p2.x;, &p2.y;);
        scanf("%lf %lf", &p3.x;, &p3.y;);

        // 抛物线 y = ax^2 + bx + c
        a = (p2.y - p1.y) / ((p2.x - p1.x)*(p2.x - p1.x));   // a = (y2-y1) / (x2-x1)^2
        b = -2 * a * p1.x;    // b = -2a*x1;
        c = p1.y - a * p1.x * p1.x - b * p1.x;   // c = y - ax^2 - bx
        //直线 y = kx + h
        k = (p2.y - p3.y) / (p2.x - p3.x);
        h = p3.y - k * p3.x;

        double s = a/3*(p3.x*p3.x*p3.x - p2.x*p2.x*p2.x) + (b-k)/2*(p3.x*p3.x-p2.x*p2.x) + (c-h)*(p3.x-p2.x);

        printf("%.2lf\n", s);
    }
    return 0;


}