MyDataStructureHomework/week4/p2.cpp at master · AtomFirst/MyDataStructureHomework · GitHub

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
#include<iostream>
#include<iomanip>
#include<vector>
#include<tuple>
#include<algorithm>
using namespace std;

#define all(x) x.begin(),x.end()

template<typename T>
struct Matrix{
    int n,m;
    vector<vector<T>> elem;

    Matrix(): n(0),m(0) {}

    friend istream& operator>>(istream& in,Matrix &mtr){
        in>>mtr.n>>mtr.m;
        mtr.elem.resize(mtr.n,vector<T>(mtr.m));
        for(auto &line:mtr.elem)
            for(auto &e:line)
                in>>e;
        return in;
    }

    friend ostream& operator<<(ostream& out,const Matrix &mtr){
        for(const auto &line:mtr.elem){
            for(const auto &e:line)
                out<<setw(2)<<e<<" ";
            out<<endl;
        }
        return out;
    }
};

template<typename T>
vector<tuple<int,int,T>> GetSaddlePoint(const Matrix<T> &mtr){
    vector<int> mn(mtr.n),mx(mtr.m);
    for(int i=0;i<mtr.n;i++)
        mn[i]=*min_element(all(mtr.elem[i]));
    for(int j=0;j<mtr.m;j++)
        for(int i=0;i<mtr.n;i++)
            mx[j]=max(mx[j],mtr.elem[i][j]);

    vector<tuple<int,int,T>> res;
    for(int i=0;i<mtr.n;i++)
        for(int j=0;j<mtr.m;j++)
            if(mtr.elem[i][j]==mn[i] and mtr.elem[i][j]==mx[j])
                res.emplace_back(i,j,mtr.elem[i][j]);
    return res;
}

int main(){
    Matrix<int> matrix;
    cin>>matrix;
    auto res=GetSaddlePoint(matrix);
    for(const auto &[r,c,e]:res)
        cout<<"("<<r<<","<<c<<","<<e<<")"<<endl;

    return 0;
}