第四届福建省大学生程序设计竞赛（部分）

旧城等待， 2022-05-27 08:53 209阅读 0赞

## 第四届福建省大学生程序设计竞赛 ##

### A.Forever 0.5 ###

FZU 2140  
题意：  
给你一个数n，让你找出n个点，满足一下关系：  
任意两点的距离不大于1.0  
所有点到原点的距离不大于1.0  
恰好有N对点的距离为1.0  
由这些点构成的n边形的面积不小于0.5  
由这些点构成的n边形的面积不大于0.75

思路：由于所有点到原点距离为1，那么首先想到的是圆。  
假设输入的点为1或者2，构不成多边形。  
当n==3时，例如图A，O，B三点（前三条符合要求），△AOB是一个等边三角形，面积为0.216506，不符合要求  
当n>=4时，把另一个点设置在C点，AB=OB=OC=1，  
四边形ACBO的面积为0.5，符合要求，那么剩下的点都放在C处即可，因为题目没有要求说不能在一处

![5ad3103d405f2.png][]

#include<cstdio> 
    #include<queue> 
    #include<cstring> 
    #include<math.h> 
    #include<algorithm> 
    using namespace std;  
    const int maxn = 35;  
    int T, n;  
    
    int main() {  
        scanf("%d", &T);  
        for (int cas = 1; cas <= T; cas++) {  
            scanf("%d", &n);  
            if (n <= 3) printf("No\n");  
            else {  
                printf("Yes\n");  
                printf("%.6lf %.6lf\n", 0.0, 0.0);  
                printf("%.6lf %.6lf\n", -0.5, sqrt(3.0) / 2);  
                printf("%.6lf %.6lf\n", 0.5, sqrt(3.0) / 2);  
                for (int i = 4; i <= n; i++) {  
                    printf("%.6lf %.6lf\n", 0.0, 1.0);  
                }  
            }  
        }  
        return 0;  
    }

## G.Easy Game ##

FZU - 2146  
题意：判断输入字符串的个数

思路：输入字符数组，然后strlen()，求长度取余判断奇偶

#include<iostream>
    #include<cstring>
    #include<cstdio>
    using namespace std;
    
    int main()
    {
        string a;
        int T;
        cin >> T;
    
        for(int i=1; i<=T; i++)
        {
            cin >> a;
            {
                printf("Case %d: ", i);
                int len = a.size();
                if(len % 2 == 0)
                {
                    cout << "Even";
                }
                else{
                    cout << "Odd";
                }
                cout << endl;
            }
        }
        return 0;
    }

## H.A-B Game ##

FZU - 2147  
题意：  
给出一个数字A和B，要求A经过变化成为A\`，A\`<=B，计算出最小需要多少次变化  
变化的公式是A-(A%x)，x是\[1,A-1\]之间的任意值

思路：需要变化的最少，那么每次减去的数字要最大，最大的时候正是x=A/2+1的时候，公式是自己推的  
例如8，8/3=5，7，7/3=4，可以看出。

#include<cstdio>
    #include<iostream>
    #include<cstring>
    typedef long long ll;
    using namespace std;
    
    int main()
    {
        int T;
        ll a,b;
        ll time;
        cin >> T;
        for(int i=1; i<=T; i++){
            time = 0;
            cin >> a >> b;
            while(a > b){
                a = a/2 + 1;
                time++;
            }
            printf("Case %d: ", i);
            cout << time << endl;
        }
        return 0;
    }

## I.Moon Game ##

FZU - 2148  
题意：给出n个点，判断出一共有多少个凸包

思路：凸包不好计算，转化为凹包计算，首先枚举出四个点，分别以其中的三个点为三角形计算出面积  
由于不知道那个点是凹点，枚举测试，如果是凹包返回false  
![5ad3251c1c66d.png][] ![5ad3251c1b61a.png][]  
如上图，左边是凹包，右边是凸包，凹包性质是S△BCD=S△ACD+S△ACB+S△ABD，凸包没有这个性质，那么通过这个性质可以排除凹包，剩下的就是凸包（题目说没有三点共线）

#include<iostream>
    #include<algorithm>
    #include<math.h>
    #include<string>
    #include<string.h>
    #include<stdio.h>
    #include<queue>
    using namespace std;
    
    const double inf=1e-6;
    struct node
    {
        int x;
        int y;
    } num[35];
    double area(node a,node b,node c) {
        return fabs(1.0*((b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x)))/2.0;
    }
    bool is_ok(node a,node b,node c,node d) {
        if(fabs(area(a,b,c)-area(a,b,d)-area(b,c,d)-area(a,c, d))<inf)
            return false;
        return true;
    }
    int main()
    {
        int T;
        scanf("%d",&T);
        int count=1;
        while(T--)
        {
            int n;
            scanf("%d",&n);
            for(int i=0; i<n; i++)
                cin>>num[i].x>>num[i].y;
            int sum=0;
            for(int i=0; i<n; i++)
                for(int j=i+1; j<n; j++)
                    for(int k=j+1; k<n; k++)
                        for(int p=k+1; p<n; p++)
                            if(is_ok(num[i],num[j],num[k],num[p])&&is_ok(num[i],num[p],num[k],num[j])&&is_ok(num[i],num[j],num[p],num[k])&&is_ok(num[p],num[j],num[k],num[i]))
                                sum++;
            printf("Case %d: ",count++);
            printf("%d\n",sum);
        }
        return 0;
    }

## K.Fire Game ##

FZU - 2150  
题意：\#代表草地，.代表空地，要求只能选择两个位置点火（火可以在时间1内向四周蔓延），输入地图，输出最短多长时间全部烧完，如果不能输出-1

思路：  
通过一个结构体存储坐标，用dis\[i\]\[j\]数组存储烧到i,j位置最短时间  
然后使用4个for循环分别表示两处点火，进行一次bfs，bfs是两个点同时进行搜索，每次搜索除了边界，草地条件外，还要判断先前烧到此位置，和现在烧的时间哪个更短，如果短，那么更新继续，然后push新的节点  
最后选出最大的数输出(dis)

#include<iostream> 
    #include<cstring> 
    #include<algorithm> 
    #include<string> 
    #include<cstdio> 
    #include<queue> 
    using  namespace std;  
    #define inf 0x3f3f3f 
    
    struct Point   
    {  
        int x;  
        int y;  
    };  
    
    int n, m;  
    char map[15][15];  
    int dis[15][15];  
    queue<Point> que;  
    int dirx[4] = { 1, -1, 0, 0 };  
    int diry[4] = { 0, 0, -1, 1 };  
    
    int bfs(int x1, int y1, int x2, int y2)  
    {  
        int xx, yy;  
        Point p1, p2, cur, nex;  
        memset(dis, inf, sizeof(dis));  
        p1.x = x1; p1.y = y1;  
        p2.x = x2; p2.y = y2;  
        dis[x1][y1] = 0;  
        dis[x2][y2] = 0;  
        que.push(p1);  
        que.push(p2);  
        while (!que.empty())  
        {  
            cur = que.front();  
            que.pop();  
            for (int i=0; i<4; i++)  
            {  
                xx = cur.x + dirx[i];  
                yy = cur.y + diry[i];  
                if (xx>=0 && xx<n && yy>=0 && yy<m && map[xx][yy]=='#' && dis[xx][yy]>dis[cur.x][cur.y]+1)  
                {  
                    dis[xx][yy] = dis[cur.x][cur.y] + 1;  
                    nex.x = xx;  
                    nex.y = yy;  
                    que.push(nex);  
                }  
            }  
        }  
        int maxx = 0;  
        for (int i = 0; i < n;i++)  
            for (int j = 0 ; j < m; j++)  
                if (map[i][j] == '#') {  
                    maxx = max(maxx, dis[i][j]);  
                }  
        return maxx;  
    }  
    
    int main()  
    {  
        int casen;  
        cin >> casen;   
        for (int cas = 1; cas <= casen; cas++)  
        {  
            while (!que.empty())  
                que.pop();  
            cin >> n >> m;  
    
            for (int i = 0; i < n; i++)  
                cin >> map[i];  
    
            int temp;  
            int ans = inf;  
            for (int i = 0; i < n;i++)  
                for (int j = 0; j < m;j++)  
                    if (map[i][j] == '#')  
                        for (int ii = 0; ii < n;ii++)  
                             for (int jj = 0; jj < m;jj++)  
                                if (map[ii][jj] == '#') {  
                                    temp = bfs(i, j, ii, jj);  
                                    ans = min(ans, temp);  
                                }  
            if (ans == inf) ans = -1;
            cout << "Case " << cas << ": " << ans << endl;  
        }  
    }

### L. OOXX Game ###

FZU - 2151  
题意：输入一串字符串，O和X，Fat brother和Maze，每人轮流选择一个O变为X，直到不能变为止，输出谁赢，F先

思路：如果O的个数为偶数那么Fat brother赢，奇数Maze赢

#include<cstdio>
    #include<iostream>
    #include<cstring>
    using namespace std;
    
    int main()
    {
        int T;
        int n,m;
        int ans = 0;
        char s;
        cin >> T;
        for(int i=1; i<=T; i++)
        {
            ans = 0;
            cin >> n >> m;
            getchar();
            for(int i=0; i<n; i++){
                for(int j=0; j<m; j++){
                    s = getchar();
                    if(s == 'O')
                    {
                        ans++;
                    }
                }
                getchar();
            }
            printf("Case %d: ", i);
            if(ans % 2 == 0){
    
                cout << "Fat brother";
            }
            else cout << "Maze";
            cout << endl;
        }
        return 0;
    }

[5ad3103d405f2.png]: https://i.loli.net/2018/04/15/5ad3103d405f2.png
[5ad3251c1c66d.png]: https://i.loli.net/2018/04/15/5ad3251c1c66d.png
[5ad3251c1b61a.png]: https://i.loli.net/2018/04/15/5ad3251c1b61a.png