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; }