ABC218

C

题意：给你两个网格s, t，里面都包含.和#，并且#会构成形状，问你能不能通过旋转90和平移操作使得两个网格里面#构成的形状相同

方法：模拟

#include<iostream>
#include<vector>
#include<cstring>

using namespace std;

const int N = 210;

int n;
char t[N][N], s[N][N], temp[N][N];
vector<pair<int, int>> sp;

int check(){
    int cnt = 0, dx, dy;
    for(int i = 0; i < n; i ++)
        for(int j = 0; j < n; j ++)
            if(t[i][j] == '#'){
                if(!cnt){
                    dx = sp[0].first - i;
                    dy = sp[0].second - j;
                    cnt ++;
                    continue;
                }
                if(i + dx != sp[cnt].first || j + dy != sp[cnt].second) return 0;
                cnt ++;
            }
        
    return cnt == sp.size();
}

int main(){
    cin >> n;
    for(int i = 0; i < n; i ++) cin >> t[i];
    for(int i = 0; i < n; i ++){
        cin >> s[i];
        for(int j = 0; j < n; j ++)
            if(s[i][j] == '#') sp.push_back({i, j});
    }
    
    for(int i = 0; i < 4; i ++){
        if(check()){
            cout << "Yes" << endl;
            return 0;
        }
        for(int c = 0; c < n; c ++)
            for(int k = n - 1; k >= 0; k --)
                temp[n - 1 - k][c] = t[c][k];
        memcpy(t, temp, sizeof t);
    }
    
    cout << "No" << endl;
}

D

题意：平面上有N个不同的点，从这些点里面选点，问你能构成多少个不同的长方形（要求他的边和x，y轴平行）

方法：枚举对角点，再二分去找另外两个点，答案需要 / 4，复杂度\(O(n^2logn)\)

#include<iostream>
#include<algorithm>

using namespace std;

const int N = 2010;

struct node{
    int x, y;
    
    bool operator<(const node &n){
        if(x != n.x) return x < n.x;
        return y <= n.y;
    }
}a[N];

int n;

int find(node x){
    int l = 0, r = n - 1;
    while(l < r){
        int mid = l + r + 1 >> 1;
        if(a[mid] < x) l = mid;
        else r = mid - 1;
    }
    
    if(a[l].x == x.x && a[l].y == x.y) return 1;
    return 0;
}

int main(){
    cin >> n;
    for(int i = 0; i < n; i ++) cin >> a[i].x >> a[i].y;
    
    sort(a, a + n);
    
    int res = 0;
    for(int i = 0; i < n; i ++)
        for(int j = 0; j < n; j ++){
            if(a[i].x == a[j].x || a[i].y == a[j].y) continue;
            int p = a[j].x, t = a[j].y;
            int x = a[i].x, y = a[i].y;
            if(find({p, y}) && find({x, t}))
                res ++;
        }
    
    cout << res / 4 << endl;
    
    return 0;
}