湖南大学第十六届程序设计竞赛（重现赛）

A题

先判断三个点是否能构成一个三角形，只有三点在同一直线上是不行的，然后用余弦定理的推论可以判断是什么类型的三角形

#include<bits/stdc++.h>
#define  maxn  1000000000 + 7
using namespace std;
typedef long long ll;
double poi[5][5];
int main()
{
    ll n;
    cin>>n;
    double x,y,z;
    while(n--)
    {
        for(int i=1;i<=3;i++)
        {
            cin>>poi[i][1]>>poi[i][2];
        }
        x=(poi[1][1]-poi[2][1])*(poi[1][1]-poi[2][1])+(poi[1][2]-poi[2][2])*(poi[1][2]-poi[2][2]);
        y=(poi[3][1]-poi[2][1])*(poi[3][1]-poi[2][1])+(poi[3][2]-poi[2][2])*(poi[3][2]-poi[2][2]);
        z=(poi[1][1]-poi[3][1])*(poi[1][1]-poi[3][1])+(poi[1][2]-poi[3][2])*(poi[1][2]-poi[3][2]);
        double t;
        if(x>z)
        {
            t=z;
            z=x;
            x=t;
        }
        if(y>z)
        {
            t=y;
            y=z;
            z=t;
        }
        if(x>y)
        {
            t=x;
            x=y;
            y=t;
        }
        double a,b,c;
        a=sqrt(x*1.00);
        b=sqrt(y*1.00);
        c=sqrt(z*1.00);
        if(a+b<=c||a+c<=b||c+b<=a)cout<<"invalid\n";
        else{
            if(x+y==z)cout<<"right\n";
            else if(x+y>z)cout<<"acute\n";
            else cout<<"obtuse\n";
        }
    }
    return 0;
}

D题

找规律，对于n个窗口，m个人，结果是1+(m-1)/n,其实也可以理解为每个人有1/n的概率站在你前面，然后共有m个人，除你之外就是(m-1)个人。

#include<bits/stdc++.h>
#define  maxn  1000000000 + 7
using namespace std;
typedef long long ll;
int main()
{
    ll m,n;
    scanf("%d%d",&n,&m);
    printf("%.8lf",1.00000000+(m-1.00000000)/n*1.00000000);
    return 0;
}

F题

签到题，高精度加法。

#include<bits/stdc++.h>
#define  maxn  1000000000 + 7
using namespace std;
typedef long long ll;
    int s[200];
int main()
{
    string a,b;
    int c;
    cin>>a>>b>>c;
    int carry=0;
    int l1,l2;
    l1=a.length();
    l2=b.length();
    int i;
    int j=50;
    s[j]=a[l1-1]-'0'+b[l1-1]-'0'+c;
    carry=s[j]/10;
    s[j]%=10;
    j--;
    for(i=l1-2;i>=0;i--)
    {
        s[j]=a[i]-'0'+b[i]-'0'+carry;
        carry=s[j]/10;
    s[j]%=10;
    j--;
    }
    if(carry)s[j]=carry;
    for(;j<=50;j++)cout<<s[j];
    return 0;
}

G题

其实输出只有三种0，1，2。两个字符串完全相同那么结果就是0，两个字符串部分相同，但是缺少前面一段或者后面一段(必须是连续的一段)那么答案是1，其他的全是2。所以我们只要分别从前往后和从后往前匹配一遍字符串即可

#include<bits/stdc++.h>
#define  maxn  1000000000 + 7
using namespace std;
typedef long long ll;
string s,t;
int main()
{
    cin>>s>>t;
    ll l1,l2;
    l1=s.length();
    l2=t.length();
    ll i,j;
    i=j=0;
    ll sum=0;
    while(i<l1&&j<l1)
    {
        if(s[i]==t[j])
        {
            i++;
            j++;
            sum++;
        }
        else break;
    }
    i=l1-1;
    j=l2-1;
    while(i>=0&&j>=0)
    {

        if(s[i]==t[j])
        {
            i--;
            j--;
            sum++;
        }
        else break;
    }
    if(sum==2*l1&&l1==l2)cout<<0<<'\n';
    else if(sum==l1||l2==sum)cout<<1<<'\n';
    else cout<<2<<'\n';
    return 0;
}

I题

题目只给了我们两个小球，因此我们只有两次失败的机会，当我们尝试失败了，我们只能从保证扔下去不会碎的楼层开始，从下往上尝试，假设我们最差的情况下最少需要扔x次，那么假如第一次失败了，我们就要从下往上挨个楼层尝试，那么就是第一次在x楼扔碎了第一颗球，此时拿第二颗球从下往上尝试刚好是x次，以此类推，如果成功了，我们第二次就要从2x-1层往下扔，为了保证不管是成功还是失败，结果都是要x次，以此类推，最高的楼层就是(x+1)x/2,当(x+1)*x/2>=n时，满足不等式的最小正整数x即为本题答案，进一步化简可以得到O(1)的表达式ans =ceil((sqrt(1 + 8 * n) - 1) / 2);

#include<bits/stdc++.h>
#define  maxn  1000000000 + 7
using namespace std;
typedef long long ll;
ll a[1000000];
int main()
{
    ll t,n;
    cin>>t;
    while(t--)
    {
        cin>>n;
        long long ans =ceil((sqrt(1 + 8 * n) - 1) / 2);
        cout<<ans<<endl;
    }
    return 0;
}