結果

問題 No.96 圏外です。
ユーザー tnakao0123tnakao0123
提出日時 2016-03-13 01:37:48
言語 C++11
(gcc 13.3.0)
結果
WA  
実行時間 -
コード長 5,179 bytes
コンパイル時間 913 ms
コンパイル使用メモリ 97,020 KB
実行使用メモリ 114,796 KB
最終ジャッジ日時 2024-09-25 11:14:05
合計ジャッジ時間 11,015 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 52 ms
100,292 KB
testcase_01 AC 50 ms
100,424 KB
testcase_02 AC 50 ms
100,292 KB
testcase_03 AC 36 ms
100,276 KB
testcase_04 AC 53 ms
100,552 KB
testcase_05 AC 55 ms
100,676 KB
testcase_06 AC 57 ms
100,892 KB
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 AC 94 ms
104,004 KB
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 TLE -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

/* -*- coding: utf-8 -*-
 *
 * 96.cc: No.96 圏外です。 - yukicoder
 */

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>
 
using namespace std;

/* constant */

const int MAX_N = 120000;
const int CX = 10000;
const int CY = 10000;
const int BXN = (CX * 2) / 10;
const int BYN = (CY * 2) / 10;

typedef long long ll;

const int INF = 1 << 30;
const ll LINF = 1LL << 60;

/* typedef */

typedef vector<int> vi;
typedef queue<int> qi;
typedef pair<int,int> pii;

template <typename T>
struct Pt {
  T x, y;

  Pt() {}
  Pt(T _x, T _y) : x(_x), y(_y) {}
  Pt(const Pt& pt) : x(pt.x), y(pt.y) {}

  bool operator==(const Pt pt) const { return x == pt.x && y == pt.y; }
  bool operator!=(const Pt pt) const { return x != pt.x || y != pt.y; }
  Pt<T> operator+(const Pt pt) const { return Pt<T>(x + pt.x, y + pt.y); }
  Pt<T> operator-() const { return Pt<T>(-x, -y); }
  Pt<T> operator-(const Pt pt) const { return Pt<T>(x - pt.x, y - pt.y); }
  Pt<T> operator*(T t) const { return Pt<T>(x * t, y * t); }
  Pt<T> operator/(T t) const { return Pt<T>(x / t, y / t); }
  T dot(Pt v) const { return x * v.x + y * v.y; }
  T cross(Pt v) const { return x * v.y - y * v.x; }
  Pt<T> mid(const Pt pt) { return Pt<T>((x + pt.x) / 2, (y + pt.y) / 2); }
  T d2() { return x * x + y * y; }
  double d() { return sqrt(d2()); }

  Pt<T> rot(double th) {
    double c = cos(th), s = sin(th);
    return Pt<T>(c * x - s * y, s * x + c * y);
  }

  Pt<T> rot90() { return Pt<T>(-y, x); }

  bool operator<(const Pt& pt) const {
    return x < pt.x || (x == pt.x && y < pt.y);
  }

  void print(string format) {
    printf(("(" + format + ", " + format + ")\n").c_str(), x, y);
  }
  void print() { print("%.6lf"); }
};

typedef Pt<int> pt;
typedef vector<pt> vpt;

struct UFT {
  int links[MAX_N], ranks[MAX_N], sizes[MAX_N];

  void clear(int n) {
    for (int i = 0; i < n; i++) links[i] = i, ranks[i] = sizes[i] = 1;
  }
  UFT() {}
  UFT(int n) { clear(n); }

  int root(int i) {
    int i0 = i;
    while (links[i0] != i0) i0 = links[i0];
    return (links[i] = i0);
  }

  int rank(int i) { return ranks[root(i)]; }
  int size(int i) { return sizes[root(i)]; }
  bool same(int i, int j) { return root(i) == root(j); }

  int merge(int i0, int i1) {
    int r0 = root(i0), r1 = root(i1), mr;
    if (r0 == r1) return r0;
    if (ranks[r0] == ranks[r1]) {
      links[r1] = r0;
      sizes[r0] += sizes[r1];
      ranks[r0]++;
      mr = r0;
    }
    else if (ranks[r0] > ranks[r1]) {
      links[r1] = r0;
      sizes[r0] += sizes[r1];
      mr = r0;
    }
    else {
      links[r0] = r1;
      sizes[r1] += sizes[r0];
      mr = r1;
    }
    return mr;
  }
};

/* global variables */

pt ps[MAX_N];
vi bps[BYN + 1][BXN + 1], cps[MAX_N];
UFT uft;
bool used[MAX_N];

/* subroutines */

void convex_hull(const vi& cp, vpt& chs) {
  int n = cp.size();
  vpt lhs, uhs;

  lhs.push_back(ps[cp[0]]);
  lhs.push_back(ps[cp[1]]);
  for (int i = 2; i < n; i++) {
    int ln = lhs.size();
    pt &lh0 = lhs[ln - 2], &lh1 = lhs[ln - 1];
    if ((lh1 - lh0).cross(ps[cp[i]] - lh1) < 0) lhs.pop_back();
    lhs.push_back(ps[i]);
  }

  uhs.push_back(ps[cp[n - 1]]);
  uhs.push_back(ps[cp[n - 2]]);
  for (int i = n - 3; i >= 0; i--) {
    int un = uhs.size();
    pt &uh0 = uhs[un - 2], &uh1 = uhs[un - 1];
    if ((uh1 - uh0).cross(ps[cp[i]] - uh1) < 0) uhs.pop_back();
    uhs.push_back(ps[i]);
  }

  lhs.pop_back();
  uhs.pop_back();

  chs.clear();
  chs.reserve(lhs.size() + uhs.size());
  chs.assign(lhs.begin(), lhs.end());
  chs.insert(chs.end(), uhs.begin(), uhs.end());
}

/* main */

int main() {
  int n;
  cin >> n;
  for (int i = 0; i < n; i++) cin >> ps[i].x >> ps[i].y;

  if (n == 0) {
    printf("%.9lf\n", 1.0);
    return 0;
  }

  for (int i = 0; i < n; i++) {
    int bx = (ps[i].x + CX) / 10, by = (ps[i].y + CY) / 10;
    bps[by][bx].push_back(i);
  }

  uft.clear(n);
  
  for (int by0 = 0; by0 <= BYN; by0++)
    for (int bx0 = 0; bx0 <= BXN; bx0++) {
      vi &bp0 = bps[by0][bx0];
      for (vi::iterator uit = bp0.begin(); uit != bp0.end(); uit++) {
	int &u = *uit;
	for (int by = by0 - 1; by <= by0 + 1; by++)
	  if (by >= 0 && by <= BYN)
	    for (int bx = bx0 - 1; bx <= bx0 + 1; bx++)
	      if (bx >= 0 && bx <= BXN) {
		vi &bp1 = bps[by][bx];
		for (vi::iterator vit = bp1.begin(); vit != bp1.end(); vit++) {
		  int &v = *vit;
		  if (uft.root(u) != uft.root(v) &&
		      (ps[v] - ps[u]).d2() <= 10 * 10)
		    uft.merge(u, v);
		}		
	      }
      }
    }

  for (int i = 0; i < n; i++) cps[uft.root(i)].push_back(i);

  int maxd2 = 0;
  
  for (int i = 0; i < n; i++) {
    vi &cpi = cps[i];
    if (cpi.size() > 1) {
      vpt chs;
      convex_hull(cpi, chs);

      int hn = chs.size();
      for (int j = 0; j < hn; j++)
	for (int k = j + 1; k < hn; k++) {
	  int d2 = (chs[k] - chs[j]).d2();
	  if (maxd2 < d2) maxd2 = d2;
	}
    }
  }

  printf("%.9lf\n", sqrt((double)maxd2) + 2.0);
  return 0;
}
0