AtCoder BC071 C : Make a Rectangle
問題
https://beta.atcoder.jp/contests/abc071/tasks/arc081_a
解法
長方形の辺の候補となるのは2本以上存在する棒です。また、4本以上存在すれば正方形にすることが出来ます(正方形は長方形に含まれる)
よって、同じ棒が2本現れる毎に辺の候補に追加し、その中から1番目に長いものと2番目に長いもので長方形を作れば解となります。
なお、辺の候補が2つ以上無ければ解無しとして0を出力します。
実装
実装としては、同じ長さの棒のカウントにはmap、辺の候補の管理はvectorで行います。
#include<iostream> #include<vector> #include<map> #include<algorithm> #include<cmath> #include<string> #define FOR(i,a,b) for(int i=(a);i<(b);++i) #define REP(i,n) FOR(i,0,n) #define MOD 1000000007 using namespace std; typedef long long int ll; const ll INF=(ll)1e18; int main(){ int N; cin >> N; map<ll, int> m; vector<ll> a; REP(i,N){ ll tmp; cin >> tmp; m[tmp]++; if(m[tmp] % 2 == 0){ a.push_back(tmp); } } if(a.size() > 1){ sort(a.begin(),a.end()); cout << a[a.size()-1] * a[a.size()-2] << endl; }else{ cout << 0 << endl; } }