第二次组队赛之：Can you find it?&&Toxophily&& Party All the Time&& Squares

Can you find it? HDU2141

题目好理解：在输入的三行数据中（必须每行取一个数）相加与输入的值比较。

如果用暴力肯定会超时的：那么把俩行合并，再二分。。。

#include<iostream>
#include<stdio.h>
#include<math.h>
#include<algorithm>
using namespace std;
int ab[501*501];
int dis(int h,int q)//二分查找
{
    int left,right,mid;
    left=0;
    right=h-1;
    while(left<=right)
    {
        mid=(left+right)/2;
        if(ab[mid]==q)
            return 1;
        else if(ab[mid]>q)
            right=mid-1;
        else if(ab[mid]<q)
            left=mid+1;
    }
    return 0;
}
int main()
{
    int cout1=1,l,m,n,a[505],b[505],c[505],i,j,h,t,d,s,q;
    while(scanf("%d%d%d",&l,&m,&n)!=EOF)
    {
        h=0;
        for(i=0;i<l;i++)
            scanf("%d",&a[i]);
        for(i=0;i<m;i++)
            scanf("%d",&b[i]);
        for(i=0;i<n;i++)
            scanf("%d",&c[i]);
        for(i=0;i<l;i++)
            for(j=0;j<m;j++)
            ab[h++]=a[i]+b[j];//合并
        sort(ab,ab+h);
       scanf("%d",&t);
        printf("Case %d:
",cout1++);
        for(i=0;i<t;i++)
        {
            d=0;
            scanf("%d",&s);
            for(j=0;j<n;j++)
            {
                q=s-c[j];
                if(dis(h,q))
                {
                    d=1;
                    break;
                }
            }
            if(d==0)
                printf("NO
");
            else if(d==1)
                printf("YES
");
        }
    }
    return 0;
}

Toxophily HDU2298

首先这是一个物理题！！（全忘记了）

再次他们是在一个平面里的！！

先是用纯粹的物理思想来做；

由x=v*cos(θ)*t,y=v*sin(θ）*t-g*t*t/2,然后通过数学变形（sin（θ）^2+cos(θ)^2=1)得到方程：

g*x*x*tan(θ）^2-2*v*v*x*tan(θ)+2*v*v*y+g*x*x=0，再用求根公式解该一元二次方程。（1+tan^2(α)=sec^2(α)， cosα ·secα=1）

#include<iostream>
#include<cstdio>
#include<cmath>

using namespace std;
const double PI=acos(-1.0);
const double g=9.8;

int main()
{
    int t;
    double x,y,v;
    double a,b,c,d,p1,p2;
    cin>>t;
    while(t--)
    {
        cin>>x>>y>>v;
        a=g*x*x;
19      b=-2*v*v*x;
20      c=2*v*v*y+g*x*x;
21      d=b*b-4*a*c;
        if(d<0)
        {
            printf("-1
");
            continue;
        }
        p1=atan((-b+sqrt(d))/a/2);
        p2=atan((-b-sqrt(d))/a/2);
        if((p1<0||p1>PI/2)&&(p2<0||p2>PI/2))
            printf("-1
");
        else if(p1<0||p1>PI/2)
            printf("%.6lf
",p2);
        else if(p2<0||p2>PI/2)
            printf("%.6lf
",p1);
        else
            printf("%.6lf
",min(p1,p2));
    }
    return 0;
}

之后方法参照：http://blog.csdn.net/hello_there/article/details/8519008

Party All the Time HDU4355

一道典型的三分题：

#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<math.h>
using namespace std;
int n;
struct line
{
    double bumanyi;
    double area;
}a[50000];
bool comp1(line x,line y)
{
    return x.area<y.area;
}
double dis(double mid)
{
    int i;
    double t;
    t=0;
    for(i=0;i<n;i++)
    {
        t+=fabs((a[i].area-mid)*(a[i].area-mid)*(a[i].area-mid))*a[i].bumanyi;
    }
    return t;
}
int main()
{
    double mid,mmid,left,right,t1,t2;
    int t,i,w=0;
    scanf("%d",&t);
    while(t--)
    {
        w++;
        scanf("%d",&n);
        for(i=0;i<n;i++)
            scanf("%lf %lf",&a[i].area,&a[i].bumanyi);
        sort(a,a+n,comp1);
        left=a[0].area;right=a[n-1].area;
        while(right-left>1e-4)//因为结果取整，精度不要太大，会超时的
        {
            mid=left/2+right/2;
            mmid=mid/2+right/2;
            t1=dis(mid);
            t2=dis(mmid);
            if(t1>t2)
                left=mid;
            else if(t1<t2)
                right=mmid;
            else
                break;

        }
        printf("Case #%d: %.lf
",w,t1);
    }
    return 0;
}

Squares POJ2002

算法过程：

1 将顶点按x坐标递增排序，若x相同，按y坐标递增排序，然后枚举所有边，对每一条由点p1和p2(根据排序p1 < p2)组成的边按照如下方式可唯一确定一个正方形：

    1) 将边绕p1逆时针旋转90度得到点p3

    2) 将边绕p2顺时针旋转90度得到点p4

则p1 p2 p3 p4组成一个正方形，设p1 = (x1,y1), p2 = (x2, y2)，根据向量的旋转公式可以求出p3, p4的坐标为

p3 = (y1 - y2 + x1, x2 - x1 + y1)

p4 = (y1 - y2 + x2, x2 - x1 + y2)

2 然后搜索点p3和p4是否存在，若存在则找到一个正方形，计数加1，可以发现总是存在两条边确定的正方形是一样的，也就是说每个正方形会被发现2次，所以要将最后的计数结果除以2.

实现的时候关键是如何搜索某个点是否存在，由于所有点都排序过，所以可以用二分查找来搜索，但速度比较慢，至少1000ms， hash的速度更快些，可以达到几百ms，还有hash表如果用开放地址线性探测法解决冲突的话，很容易超时，

而用链地址法解决冲突效果要好很多。下面是二分搜索和hash两种方法的代码实现。

貌似那些会超时的程序可以用二分法或三分法来压缩时间（个人猜测！！）

#include<iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;
int n;
struct line
{
    int x;
    int y;
}a[1005];
bool comp1(line i,line j)
{
    if(i.x<j.x)
        return true;
    else if(i.x==j.x)
    {
        if(i.y<j.y)
            return true;
    }
    return false;
}
int chazhao(int i,int j)
{
    int left,right,mid;
    left=0;
    right=n-1;
    while(left<=right)
    {
        mid=(left+right)/2;
        if(i==a[mid].x&&j==a[mid].y)
            return 1;
        else if(i<a[mid].x||(i==a[mid].x&&j<a[mid].y))
            right=mid-1;
        else
            left=mid+1;
    }
    return 0;
}
int main()
{
    int sum,i,j,x,y;
    while(scanf("%d",&n)!=EOF)
    {
        if(n==0)
            break;
        sum=0;
        for(i=0;i<n;i++)
            scanf("%d %d",&a[i].x,&a[i].y);
        sort(a,a+n,comp1);//排序
        for(i=0;i<n;i++)
            for(j=i+1;j<n;j++)
        {
            x=a[i].y-a[j].y+a[i].x;
            y=a[j].x-a[i].x+a[i].y;
            if(chazhao(x,y)==0)
                continue;
            x=a[i].y-a[j].y+a[j].x;
            y=a[j].x-a[i].x+a[j].y;
            if(chazhao(x,y))
                sum++;
        }
        printf("%d
",sum/2);
    }
    return 0;
}//从前俩个点来判断第三第四个点是否存在