結果

問題 No.96 圏外です。
ユーザー imgry22imgry22
提出日時 2014-12-19 20:03:15
言語 C++11
(gcc 11.4.0)
結果
RE  
実行時間 -
コード長 2,878 bytes
コンパイル時間 2,380 ms
コンパイル使用メモリ 166,664 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-06-12 01:50:58
合計ジャッジ時間 4,910 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
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 RE -
testcase_05 RE -
testcase_06 WA -
testcase_07 RE -
testcase_08 WA -
testcase_09 RE -
testcase_10 RE -
testcase_11 RE -
testcase_12 RE -
testcase_13 WA -
testcase_14 RE -
testcase_15 WA -
testcase_16 WA -
testcase_17 RE -
testcase_18 RE -
testcase_19 WA -
testcase_20 RE -
testcase_21 WA -
testcase_22 RE -
testcase_23 RE -
testcase_24 AC 2 ms
5,376 KB
testcase_25 RE -
testcase_26 RE -
testcase_27 RE -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;

typedef long long int ll;
typedef unsigned long long int llu;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pair<int, int> > vii;

#define rrep(i, m, n) for(int i=m; i<n;  i++)
#define erep(i, n)    for(int i=1; i<=n; i++)
#define  rep(i, n)    for(int i=0; i<n;  i++)
#define rrev(i, m, n) for(int i=n-1; i>=m; i--)
#define erev(i, n)    for(int i=n; i>=1; i--)
#define  rev(i, n)    for(int i=n-1; i>=0; i--)
#define EACH(v)       (v).begin(), (v).end()
#define CNT(a, n, x)  (upper_bound(a, a+n, x)-lower_bound(a, a+n, x))
#define mp            make_pair
template<class T1, class T2> inline void minup(T1 &m, T2 x){ if(m>x) m=static_cast<T2>(x); }
template<class T1, class T2> inline void maxup(T1 &m, T2 x){ if(m<x) m=static_cast<T2>(x); }

#define INF 1000000000
#define MOD 1000000009
#define EPS 1E-9

typedef complex<int> P;
int dot(P p, P q){ return real(p*conj(q)); }
int det(P p, P q){ return imag(p*conj(q)); }

#define MAX_N 1000

int n;
int x, y;
P z[MAX_N];
double res;

int dist(P z, P w) { return real(z-w)*real(z-w)+imag(z-w)*imag(z-w); }
bool check(P z, P w) { return dist(z, w) <= 100; }

struct UnionFind
{
  vi data;
  UnionFind(int size) : data(size, -1) {}
  bool unite(int x, int y){
    x = root(x);
    y = root(y);
    if(x != y){
      if(data[y] < data[x]) swap(x, y);
      data[x] += data[y];
      data[y] = x;
    }
    return x != y;
  }
  bool same(int x, int y){ return root(x) == root(y); }
  int root(int x){ return data[x] < 0 ? x : data[x] = root(data[x]); }
  int size(int x){ return -data[root(x)]; }
};

bool compare(const P& p, const P& q)
{
  return p.real() != q.real() ? p.real() < q.real() : p.imag() < q.imag();
}

vector<P> convex_hull(P* ps, int n)
{
  sort(ps, ps + n, compare);
  int k = 0;
  vector<P> qs(n * 2);

  rep(i, n){
    while(k>1 && det((qs[k-1]-qs[k-2]), (ps[i]-qs[k-1])) <= 0) k--;
    qs[k++] = ps[i];
  }

  int t = k;
  rev(i, n-1){
    while(k>t && det((qs[k-1]-qs[k-2]), (ps[i]-qs[k-1])) <= 0) k--;
    qs[k++] = ps[i];
  }
  qs.resize(k - 1);
  return qs;
}

int main()
{
  cin >> n;
  rep(i, n){
    cin >> x >> y;
    z[i] = P(x, y);
  }

  if(n==0){
    puts("1");
    return 0;
  }

  vector<P> pque = convex_hull(z, n);
  UnionFind uf(n);
  rep(i, pque.size()) rep(j, i) if(check(pque[i], pque[j]))   uf.unite(i, j);

  int n = pque.size();
  if(n == 2){
    printf("%.10f\n", 2 + (check(pque[0], pque[1]) ? sqrt(dist(pque[0], pque[1])) : 0));
    return 0;
  }
  int i=0, j=0;

  rep(k, n){
    if(!compare(pque[i], pque[k])) i = k;
    if( compare(pque[j], pque[k])) j = k;
  }

  int si = i;
  int sj = j;
  while(i!=sj || j!=si){
    maxup(res, dist(pque[i], pque[j]));
    if(det(pque[(i+1)%n] - pque[i], pque[(j+1)%n] - pque[j]) < 0) i = (i+1)%n;
    else j = (j+1)%n;
  }

  printf("%.10f\n", sqrt(res) + 2.0);

  return 0;
}
0