首页 > ACM题库 > HDU-杭电 > HDU 4752-Polygon-计算几何-[解题报告]HOJ
2015
09-17

HDU 4752-Polygon-计算几何-[解题报告]HOJ

Polygon

问题描述 :

  In this problem, you’re given a function f(x) = ax^2 + bx + c(x in [l, r]) and a simple polygon. And we need you to figure out the length of f(x) in this polygon.

输入:

  There are several test cases and the cases end with EOF. For each case:

  The first line contains six integers n (1 <= n <= 20000), a(a != 0), b, c, l and r, which are the total of the points of the polygon and the parameters of the function and these parameters are in the range [-20000, 20000].

  The next n lines contains two integers x and y, which are the coordinate of the point and both of them are in the range[-10^9, 10^9]. We can ensure that there is a edge between i-th point and (i+1)-th point (1 <= i < n) and there is a edge between first point and n-th point.

输出:

  There are several test cases and the cases end with EOF. For each case:

  The first line contains six integers n (1 <= n <= 20000), a(a != 0), b, c, l and r, which are the total of the points of the polygon and the parameters of the function and these parameters are in the range [-20000, 20000].

  The next n lines contains two integers x and y, which are the coordinate of the point and both of them are in the range[-10^9, 10^9]. We can ensure that there is a edge between i-th point and (i+1)-th point (1 <= i < n) and there is a edge between first point and n-th point.

样例输入:

4 1 0 0 -100 100
-10 0
10 0
10 10
-10 10

样例输出:

21.52

http://acm.hdu.edu.cn/showproblem.php?pid=4752


数学题,题目大意是给一条抛物线,然后还定义域,再给n个点,从第i个点连接到第(i+1)个点,然后最后一个点和第一个点连接,最后构成一个n边形,然后要求的是抛物线落在n边形里面的弧长长度的总和。
本来是想一段一段求出来的,可是想了半天都没想出要怎么做出来,后来看了别人的代码,才发现原来是用 多还少补 的思想。
思路大概是这样的:
先考虑第 i 和 (i-1) 个点构成的线段是否垂直于x轴,如果垂直,则这条线是用于辅助将多边形包围进去,无需计算,如果不是,就开始求交点,交点可能有一个也有可能有两个,或者没有,有交点的情况,可以直接当初有两个交点来考虑,然后就可以把一条线段分成三段。计算的时候,要分成一段一段的线段来求,先不考虑是否多加的情况,只要抛物线在线段下方,由线段端点或者原来抛物线的定义域来确定左右区间,然后计算的话,就是定积分的问题了,套套公式就可以了,如果上一条线段是垂直于x轴,且端点正好在抛物线上,这种情况也还是可以算的,不会漏掉。然后这样肯定是会多算的,所以我们得把多算的扣掉,然后就是通过规定方向来将多余的扣掉的,方向随便规定,我这边规定的是从右往左是正方向,这样如果我们多加了,因为要最后要首尾相连,肯定有一些算出来是反方向的,正好可以把多算的抵消掉。然后如果是没有交点的,只需要考虑线段是否在抛物线的上方,如果在,只有两种情况,一种是因为前面有一条垂直于x轴的线段,或者抛物线定义域的限制,直接计算一下就可以了。最后还有一点需要注意,因为是有规定方向的,然后将点给的顺序颠倒一下,得到的结果就是原来的相反数了,所以最后的结果别忘了取个绝对值。

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;

const int maxn = 20005;

typedef struct POINT
{
    int x;
    int y;
}Point;

int n;
Point point[maxn];
long double a, b, c, L, R;

inline long double sqr(long double x)
{
    return x * x;
}

//用于计算定积分
long double f(long double x)
{
    long double temp = sqrt( sqr(b + 2*a*x) + 1 );
    return ( (b + 2*a*x)*temp + log(b + 2*a*x + temp) ) / (a*4);
}

//计算两点之间的抛物线的长度
long double calc( long double x0, long double y0, long double x1, long double y1 )
{    
    //如果抛物线位于这条线段上方,易知不用计算
    double xx = (x0 + x1) / 2;
    if ( a * xx * xx + b * xx + c > (y0 + y1) / 2 )
        return 0;

    //更新左右端点
    //如果只有一个交点,这边显然算出来是0。
    long double l = max( L, x0 );
    long double r = min( R, x1 );

    return l < r ? f(r) - f(l) : 0;
}

int main()
{
    //固定的浮点数显示
    cout << fixed;
    //设置精度为小数点后两位
    cout.precision(2);

    while (cin >> n)
    {
        cin >> a >> b >> c >> L >> R;
        for (int i = 1; i <= n; i++ ) 
            scanf( "%d%d", &point[i].x, &point[i].y );
        point[0].x = point[n].x;
        point[0].y = point[n].y;
        long double ans = 0;
        for ( int i = 1; i <= n; i++ )
            //要计算抛物线在多边形里面的长度,线段肯定不能是垂直于x轴,
            //就算是与抛物线有交点,也只是辅助将抛物线包围进去
            if ( point[i].x != point[i-1].x )
            {
                long double x0 = point[i-1].x, y0 = point[i-1].y;
                long double x1 = point[i].x, y1 = point[i].y;
                long double k = ( y1 - y0) / ( x1 - x0 );
                long double d = y0 - k * x0;
                long double dat = sqr(b - k) - 4 * a * (c - d);
                long double length = 0;

                //确保 x0 在 x1 左边
                if ( x0 > x1 )        
                {
                    swap( x0, x1 );
                    swap( y0, y1 );
                }

                if ( dat >= 0 )
                {
                    long double x2 = ( -(b - k) + sqrt(dat) ) / (2 * a);
                    long double x3 = ( -(b - k) - sqrt(dat) ) / (2 * a);

                    //确保 x2,x3 落在 x0 与 x1 之间,并且 x2 在 x3 左边
                    if ( x2 < x0 )
                        x2 = x0;
                    if ( x2 > x1 )
                        x2 = x1;
                    if ( x3 < x0 )
                        x3 = x0;
                    if ( x3 > x1 )
                        x3 = x1;
                    if ( x2 > x3 )
                        swap(x2, x3);

                    long double y2 = k * x2 + d, y3 = k * x3 + d;
                    length += calc( x0, y0, x2, y2 );
                    length += calc( x2, y2, x3, y3 );
                    length += calc( x3, y3, x1, y1 );
                }
                //如果没有交点的话,只需要考虑抛物线是否在这个线段的上方即可
                //如果线段在上方的话,因为抛物线本来的定义域的限制,
                //或者前一条线段是垂直于x轴的,所以还是要计算的
                else
                    length += calc( x0, y0, x1, y1 );

                //因为这种求法是一段一段考虑的,然后肯定会多加了,或者多减了,
                //所以得考虑好方向,然后相应地减掉或者是加上原来多了或者是少了的抛
                //物线的长度,最后从最后一个点连到第一个点才能正好算出抛物线的长度
                if ( point[i-1].x < point[i].x )
                    ans -= length;
                else
                    ans += length;
            }
        //这种思路,如果把点给的顺序颠倒过来的话,求出来的ans是
        //原来求的ans的相反数,所以得取个绝对值。
        cout << abs(ans) << endl;
    }
    return 0;
}

参考:http://blog.csdn.net/u014683696/article/details/23564901