A. Image Scaling (模拟)

时间复杂度：$O(n \cdot m)$

题意

​ ​ ​ ​ 给定 $n \times m$ 的矩阵，只包含字符 “$.$” 和 “$x$” ，保证有且只有一个由 $x$ 构成的子矩阵，请对该子矩阵等比例缩小，并输出最终的矩阵 .

数据范围

  • $1 \le n,m \le 500$

思路

​ ​ ​ ​ 首先需定位子矩阵，通过遍历找到该子矩阵的四个端点，此时便能确定子矩阵的长和宽 .

​ ​ ​ ​ 由于是等比例缩小，不难想到，若长度为 $len$ ，宽度为 $wid$ ，则缩小后的长和宽分别为$\dfrac{len}{gcd(len,wid)}$ 和$\dfrac{wid}{gcd(len,wid)}$ ，确定好长和宽后输出最终由 $x$ 构成的结果即可 .

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include<bits/stdc++.h>
#define endl '\n' 
using i64 = long long;
using namespace std;
char s[505][505];
signed main(){
    std::ios::sync_with_stdio(false);cin.tie(0);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n;i++)
        cin >> s[i] + 1;
    int sx, sy, tx, ty;
    bool ok = 1;
    for (int i = 1; i <= n;i++){
        for (int j = 1; j <= m;j++)
            if(s[i][j]=='x'){
                sx = i, sy = j;
                ok = 0;
                break;
            }
        if(!ok)
            break;
    }
    for (int i = sx; i <= n + 1; i++)
        if(s[i][sy]!='x'){
            tx = i - 1;
            break;
        }
    for (int i = sy; i <= m + 1;i++)
        if(s[sx][i]!='x'){
            ty = i - 1;
            break;
        }
    int len = tx - sx + 1, wid = ty - sy + 1;
    //cout << sx << ' ' << sy << ' ' << tx << ' ' << ty << endl;
    auto gcd = [&](auto gcd, int a, int b) -> int
    {
        return b == 0 ? a : gcd(gcd, b, a % b);
    };
    int g = gcd(gcd, len, wid);
    len /= g, wid /= g;
    for (int i = 1; i <= len;i++){
        for (int j = 1; j <= wid;j++)
            cout << "x";
        cout << endl;
    }    
    return 0;
}

H. Two Convex Polygons（计算几何）

题意

​ ​ ​ ​ ​ 在二维平面上，给定两个凸多边形$ A , B$ ，其中 $A$ 是固定不动的。对 $B$ 进行平移、旋转或翻转，但需确保 $A$ 与 $B$ 至少有一个共同点。给定 $n$ 和 $m$ 个顶点坐标，分别表示 $A$ 和 $B$ 的顶点。求由多边形 $B$ 可能覆盖的点组成的图的周长 .

数据范围

  • $3 \le n,m \le 10^6$
  • $-10^8 \le x_i,y_i \le 10^8$

分析

​ ​ ​ ​ ​ 由于$B$的顶点能在$A$的任何区域移动，则其覆盖的区域一定包含了整个$A$的大小，想要最大化地覆盖外面的区域，不难想到，将$B$的某一顶点沿着图形$A$的边沿”滑动”，为使得覆盖最大化，那么该顶点应为$B$的凸包直径的所在点，最终类似以圆的半径形式平移变换，如下图所示 .

​ ​ ​ ​ ​ 易知，设$B$的凸包的直径为 $d$ ，$A$的周长为$C$ ,在拐角处的周长总和为半径为$d$ 的整个圆周周长，而非拐角处相当于$B$的凸包在$A$的各个边上不断平移，则最终的总周长为$2 \times \pi \times d+C$ .

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include<bits/stdc++.h>
#define endl '\n' 
using i64 = long long;
const double eps = 1E-8;
const double pi = acos(-1);
using namespace std;
int sgn(double x){
    if(fabs(x)<eps)
        return 0;
    return (x > 0 ? 1 : -1);
}
struct Point{
    double x, y;
    Point(double x = 0, double y = 0) : x(x), y(y) {}
    Point operator+(const Point &a){
        return Point(x + a.x, y + a.y);
    }
    Point operator-(const Point &a){
        return Point(x - a.x, y - a.y);
    }
    double operator^(const Point &a){
        return x * a.y - y * a.x;
    }
    bool operator==(const Point &a){
        return sgn(x - a.x) == 0 && sgn(y - a.y) == 0;
    }
    bool operator<(const Point &a){
        return sgn(x - a.x) == 0 ? y < a.y : x < a.x;
    }
};
double dis(Point a,Point b){
    return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
vector<Point> getHull(vector<Point>p){
    sort(p.begin(), p.end(), [&](auto a, auto b)
         { return sgn(a.x - b.x) == 0 ? a.y < b.y : a.x < b.x; });
    p.erase(unique(p.begin(), p.end()), p.end());
    if(p.size()<=1)
        return p;
    vector<Point> h, l;
    for(auto a:p){
        while (h.size() > 1 && ((a - h.back()) ^ (a - h[h.size() - 2])) <= 0)
            h.pop_back();
        while (l.size() > 1 && ((a - l.back()) ^ (a - l[l.size() - 2])) >= 0)
            l.pop_back();
        l.push_back(a), h.push_back(a);
    }
    l.pop_back();
    reverse(h.begin(), h.end());
    h.pop_back();
    l.insert(l.end(), h.begin(), h.end());
    return l;
}
double RotateCalipers(vector<Point>ch,int n){
    double ans = -1E18;
    int q = 1;
    Point cnt = ch[0];
    ch.push_back(cnt);
    for (int i = 0; i < n;i++){
        while (((ch[q] - ch[i + 1]) ^ (ch[i] - ch[i + 1])) < ((ch[q + 1] - ch[i + 1]) ^ (ch[i] - ch[i + 1])))
            q = (q + 1) % n;
        ans = max(ans, max(dis(ch[q], ch[i]), dis(ch[q + 1], ch[i + 1])));
    }
    return ans;
}
signed main(){
    std::ios::sync_with_stdio(false);cin.tie(0);
    int t;
    cin >> t;
    while(t--){
        int n, m;
        double ans = 0;
        cin >> n;
        vector<Point> a, b, resa, resb;
        for (int i = 0; i < n;i++){
            Point t;
            cin >> t.x >> t.y;
            a.push_back(t);
        }
        Point aa = a[0];
        int numa = a.size();
        a.push_back(aa);
        for (int i = 0; i < numa;i++)
            ans += dis(a[i], a[i + 1]);
        cin >> m;
        for (int i = 0; i < m;i++){
            Point t;
            cin >> t.x >> t.y;
            b.push_back(t);
        }
        resb = getHull(b);
        int numb = resb.size();
        double radius = RotateCalipers(resb, numb);
        ans += 2 * pi * radius;
        cout << fixed << setprecision(12) << ans << endl;
    }
    return 0;
}