#5104 (C++11) No.94 圏外です。(EASY)

提出ソース

結果

問題	No.94 圏外です。(EASY)
ユーザー	Komaki__
提出日時	2014-12-07 19:31:49
言語	C++11 (gcc 11.4.0)
結果	AC
実行時間	31 ms / 5,000 ms
コード長	5,036 bytes
コンパイル時間	1,570 ms
コンパイル使用メモリ	163,728 KB
実行使用メモリ	5,376 KB
最終ジャッジ日時	2024-06-26 07:18:31
合計ジャッジ時間	2,912 ms
ジャッジサーバーID （参考情報）	judge4 / judge2

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	2 ms 5,376 KB
testcase_02	AC	2 ms 5,376 KB
testcase_03	AC	2 ms 5,376 KB
testcase_04	AC	2 ms 5,376 KB
testcase_05	AC	3 ms 5,376 KB
testcase_06	AC	5 ms 5,376 KB
testcase_07	AC	9 ms 5,376 KB
testcase_08	AC	16 ms 5,376 KB
testcase_09	AC	30 ms 5,376 KB
testcase_10	AC	30 ms 5,376 KB
testcase_11	AC	29 ms 5,376 KB
testcase_12	AC	30 ms 5,376 KB
testcase_13	AC	29 ms 5,376 KB
testcase_14	AC	31 ms 5,376 KB
testcase_15	AC	30 ms 5,376 KB
testcase_16	AC	31 ms 5,376 KB
testcase_17	AC	31 ms 5,376 KB
testcase_18	AC	31 ms 5,376 KB
testcase_19	AC	27 ms 5,376 KB
testcase_20	AC	2 ms 5,376 KB
testcase_21	AC	2 ms 5,376 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#ifdef KOMAKI_LOCAL
#include <omp.h>
#else
#define NDEBUG
#endif

#include <bits/stdc++.h>
#include <sys/time.h>
#include <unistd.h>
using namespace std;
#define i64         int64_t
#define rep(i, n)   for(i64 i = 0; i < ((i64)(n)); ++i)
#define sz(v)       ((i64)((v).size()))
#define bit(n)      (((i64)1)<<((i64)(n)))
#define all(v)      (v).begin(), (v).end()

template <int POS, class TUPLE> void deploy(std::ostream &os, const TUPLE &tuple){}
template <int POS, class TUPLE, class H, class ...Ts> void deploy(std::ostream &os, const TUPLE &t){ os << (POS == 0 ? "" : ", ") << get<POS>(t); deploy<POS + 1, TUPLE, Ts...>(os, t); }
template <class ...Ts> std::ostream& operator<<(std::ostream &os, const std::tuple<Ts...> &t){ os << "("; deploy<0, std::tuple<Ts...>, Ts...>(os, t); os << ")"; return os; }
template <class T> std::ostream& operator<<(std::ostream &os, std::vector<T> &v){ int remain = v.size(); os << "{"; for(auto e: v) os << e << (--remain == 0 ? "" : ", "); os << "}"; return os; }
template <class T> std::ostream& operator<<(std::ostream &os, std::set<T> &v){ int remain = v.size(); os << "{"; for(auto e: v) os << e << (--remain == 0 ? "" : ", "); os << "}"; return os; }
template <class T> std::ostream& operator<<(std::ostream &os, std::queue<T> &q){ auto qq = q; os << "{"; for(; !qq.empty(); qq.pop()){ os << qq.front() << (qq.size() != 1 ? ", " : ""); } os << "}"; return os; }
template <class T> std::ostream& operator<<(std::ostream &os, std::priority_queue<T> &q){ auto qq = q; os << "{"; for(; !qq.empty(); qq.pop()){ os << qq.top() << (qq.size() != 1 ? ", " : ""); } os << "}"; return os; }
template <class T, class K> std::ostream& operator<<(std::ostream &os, std::pair<T, K> &p){ os << "(" << p.first << ", " << p.second << ")"; return os; }
template <class T, class K> std::ostream& operator<<(std::ostream &os, std::map<T, K> &mp){ int remain = mp.size(); os << "{"; for(auto e: mp) os << "(" << e.first << " -> " << e.second << ")" << (--remain == 0 ? "" : ", "); os << "}"; return os; }
template <class T, class K> std::ostream& operator<<(std::ostream &os, std::unordered_map<T, K> &mp){ int remain = mp.size(); os << "{"; for(auto e: mp) os << "(" << e.first << " -> " << e.second << ")" << (--remain == 0 ? "" : ", "); os << "}"; return os; }
#define DEBUG0() { char buf[1000]; sprintf(buf, "line:%3d | ", __LINE__); std::cout << buf << std::endl; }
#define DEBUG1(var0) { char buf[1000]; sprintf(buf, "line:%3d | ", __LINE__); std::cout << buf << (#var0) << "=" << (var0) << std::endl; }
#define DEBUG2(var0, var1) { char buf[1000]; sprintf(buf, "line:%3d | ", __LINE__); std::cout << buf << (#var0) << "=" << (var0) << ", " << (#var1) << "=" << (var1) << std::endl; }
#define DEBUG3(var0, var1, var2) { char buf[1000]; sprintf(buf, "line:%3d | ", __LINE__); std::cout << buf << (#var0) << "=" << (var0) << ", " << (#var1) << "=" << (var1) << ", " << (#var2) << "=" << (var2) << std::endl; }
#define DEBUG4(var0, var1, var2, var3) { char buf[1000]; sprintf(buf, "line:%3d | ", __LINE__); std::cout << buf << (#var0) << "=" << (var0) << ", " << (#var1) << "=" << (var1) << ", " << (#var2) << "=" << (var2) << ", " << (#var3) << "=" << (var3) << std::endl; }
#define DEBUG5(var0, var1, var2, var3, var4) { char buf[1000]; sprintf(buf, "line:%3d | ", __LINE__); std::cout << buf << (#var0) << "=" << (var0) << ", " << (#var1) << "=" << (var1) << ", " << (#var2) << "=" << (var2) << ", " << (#var3) << "=" << (var3) << ", " << (#var4) << "=" << (var4) << std::endl; }
#define DEBUG6(var0, var1, var2, var3, var4, var5) { char buf[1000]; sprintf(buf, "line:%3d | ", __LINE__); std::cout << buf << (#var0) << "=" << (var0) << ", " << (#var1) << "=" << (var1) << ", " << (#var2) << "=" << (var2) << ", " << (#var3) << "=" << (var3) << ", " << (#var4) << "=" << (var4) << ", " << (#var5) << "=" << (var5) << std::endl; }

















class UnionFind
{
public:
  int getGroupId(int index);
  void putTogether(int index0, int index1);

  UnionFind();
  UnionFind(int size);

private:
  int size;
  std::vector<int> parents;
};

inline UnionFind::UnionFind()
{
}

inline UnionFind::UnionFind(int size)
{
  this->size = size;
  parents = std::vector<int>(size);
  for(int i = 0; i < size; ++i){
    parents[i] = i;
  } 
}

inline void UnionFind::putTogether(int index0, int index1)
{
  parents[getGroupId(index0)] = getGroupId(index1);
}

inline int UnionFind::getGroupId(int index)
{
  if(parents[index] == index) return index;
  return parents[index] = getGroupId(parents[index]);
}


int main()
{
  i64 n;
  cin >> n;
  vector<i64> x(n), y(n);
  rep(i, n) cin >> x[i] >> y[i];

  UnionFind uf(n);
  rep(i, n)rep(j, n){
    if(hypot(x[i] - x[j], y[i] - y[j]) <= 10.00001) uf.putTogether(i, j);
  }

  double ans = 1;
  rep(i, n)rep(j, n)if(uf.getGroupId(i) == uf.getGroupId(j)){
    ans = max(ans, 2 + hypot(x[i] - x[j], y[i] - y[j]));
  }
  printf("%0.20lf\n", ans);
}

yukicoder

結果

テストケース

ソースコード