首页 > ACM题库 > HDU-杭电 > hdu 2298 Toxophily -分治-[解题报告]C++
2014
01-05

hdu 2298 Toxophily -分治-[解题报告]C++

Toxophily

问题描述 :

The recreation center of WHU ACM Team has indoor billiards, Ping Pang, chess and bridge, toxophily, deluxe ballrooms KTV rooms, fishing, climbing, and so on.
We all like toxophily.

Bob is hooked on toxophily recently. Assume that Bob is at point (0,0) and he wants to shoot the fruits on a nearby tree. He can adjust the angle to fix the trajectory. Unfortunately, he always fails at that. Can you help him?

Now given the object’s coordinates, please calculate the angle between the arrow and x-axis at Bob’s point. Assume that g=9.8N/m.

输入:

The input consists of several test cases. The first line of input consists of an integer T, indicating the number of test cases. Each test case is on a separated line, and it consists three floating point numbers: x, y, v. x and y indicate the coordinate of the fruit. v is the arrow’s exit speed.
Technical Specification

1. T ≤ 100.
2. 0 ≤ x, y, v ≤ 10000.

输出:

The input consists of several test cases. The first line of input consists of an integer T, indicating the number of test cases. Each test case is on a separated line, and it consists three floating point numbers: x, y, v. x and y indicate the coordinate of the fruit. v is the arrow’s exit speed.
Technical Specification

1. T ≤ 100.
2. 0 ≤ x, y, v ≤ 10000.

样例输入:

3
0.222018 23.901887 121.909183
39.096669 110.210922 20.270030
138.355025 2028.716904 25.079551

样例输出:

1.561582
-1
-1

首先推出一个非线性的凸性函数,f(x)=a/cos(x)/cos(x)+b*tan(x)+c (x是弧度);

然后利用三分查找函数是否有解;

最后如果有节,二分查找左边的解。


ACcode:

#include<cstdio>
#include<cstring>
#include<cmath>

const double pi=acos(-1.0);
const double eps=1e-12;

double a,b,c;
double x,y,v,vx,vy;

double cal(double p)
{
    double tmp=a/(cos(p)*cos(p))+b*tan(p)+c;
    return tmp;
}

double trisection(double &down,double &up)
{
    double left,right,xl,xr;
    while ((up-down)>eps)
    {
        left=(up+down+down)/3.0;
        right=(up+up+down)/3.0;
        xl=cal(left),xr=cal(right);
        if (xl<0) return left;
        if (xr<0) return right;
        if (xl<xr) up=right;
        else down=left;
    }
    return -1.0;
}

double dbs(double tmp)
{
    return tmp>0?tmp:-tmp;
}

double binary(double down,double up)
{
    double t,mid;
    while ((up-down)>eps)
    {
        mid=(down+up)/2.0;
        t=cal(mid);
        if (t>0) down=mid;
        else up=mid;
    }
    return mid;
}

int main()
{
    int T;
    scanf("%d",&T);
    while (T--)
    {
        scanf("%lf%lf%lf",&x,&y,&v);
        a=4.9*x*x/v/v,b=-x,c=y;
        double m1=0.0,m3=pi/2.0-eps;
        double m2=trisection(m1,m3);
        if (m2>0)
        {
            x=binary(m1,m2);
            printf("%lf\n",x);
        }
        else printf("%.0lf\n",m2);
    }
    return 0;
}

解题转自:http://blog.csdn.net/cxsmile/article/details/8885235


  1. 漂亮。佩服。
    P.S. unsigned 应该去掉。换行符是n 不是/n
    还可以稍微优化一下,
    int main() {
    int m,n,ai,aj,bi,bj,ak,bk;
    while (scanf("%d%d",&m,&n)!=EOF) {
    ai = sqrt(m-1);
    bi = sqrt(n-1);
    aj = (m-ai*ai-1)>>1;
    bj = (n-bi*bi-1)>>1;
    ak = ((ai+1)*(ai+1)-m)>>1;
    bk = ((bi+1)*(bi+1)-n)>>1;
    printf("%dn",abs(ai-bi)+abs(aj-bj)+abs(ak-bk));
    }
    }

  2. Often We don’t set up on weblogs, but I would like to condition that this established up really forced me individually to do this! considerably outstanding publish

  3. L(X [0 .. M-1],Y [0 .. N-1])= 1 + L(X [0 .. M-2],Y [0 .. N-1])这个地方也也有笔误
    应改为L(X [0 .. M-1],Y [0 .. N-1])= 1 + L(X [0 .. M-2],Y [0 .. N-2])

  4. 第一句可以忽略不计了吧。从第二句开始分析,说明这个花色下的所有牌都会在其它里面出现,那么还剩下♠️和♦️。第三句,可以排除2和7,因为在两种花色里有。现在是第四句,因为♠️还剩下多个,只有是♦️B才能知道答案。