結果

問題 No.96 圏外です。
ユーザー imgry22imgry22
提出日時 2015-01-24 19:21:18
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 398 ms / 5,000 ms
コード長 3,769 bytes
コンパイル時間 1,779 ms
コンパイル使用メモリ 174,120 KB
実行使用メモリ 83,968 KB
最終ジャッジ日時 2024-06-06 15:55:11
合計ジャッジ時間 5,226 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 5 ms
11,904 KB
testcase_01 AC 6 ms
11,896 KB
testcase_02 AC 6 ms
11,904 KB
testcase_03 AC 5 ms
11,520 KB
testcase_04 AC 9 ms
12,032 KB
testcase_05 AC 10 ms
12,160 KB
testcase_06 AC 12 ms
12,288 KB
testcase_07 AC 18 ms
12,288 KB
testcase_08 AC 19 ms
12,544 KB
testcase_09 AC 27 ms
12,800 KB
testcase_10 AC 39 ms
13,056 KB
testcase_11 AC 45 ms
13,312 KB
testcase_12 AC 58 ms
13,848 KB
testcase_13 AC 96 ms
14,464 KB
testcase_14 AC 99 ms
14,592 KB
testcase_15 AC 159 ms
16,128 KB
testcase_16 AC 143 ms
15,944 KB
testcase_17 AC 149 ms
16,768 KB
testcase_18 AC 191 ms
17,024 KB
testcase_19 AC 190 ms
17,008 KB
testcase_20 AC 176 ms
27,796 KB
testcase_21 AC 155 ms
24,188 KB
testcase_22 AC 398 ms
83,968 KB
testcase_23 AC 386 ms
83,968 KB
testcase_24 AC 6 ms
11,776 KB
testcase_25 AC 100 ms
15,488 KB
testcase_26 AC 123 ms
16,468 KB
testcase_27 AC 105 ms
15,804 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int ccw(P, P, P)’:
main.cpp:45:1: warning: control reaches end of non-void function [-Wreturn-type]
   45 | }
      | ^

ソースコード

diff # 

// kroton 氏の回答を参考に.....

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

typedef long long int ll;
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, m, n) for(int (i)=(m); (i)<=(n); (i)++)
#define  rep(i, n)    for(int (i)=0; (i)<(n);  (i)++)
#define  rev(i, n)    for(int (i)=(n)-1; (i)>=0; (i)--)
#define vrep(i, c)    for(__typeof((c).begin())i=(c).begin(); i!=(c).end(); i++)
#define  ALL(v)       (v).begin(), (v).end()
#define mp            make_pair
#define pb            push_back
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 1000000007
#define EPS 1E-12

typedef complex<double> P;

namespace std
{
  bool operator < (const P& a, const P& b) {
    return real(a) != real(b) ? real(a) < real(b) : imag(a) < imag(b);
  }
}
double dot(const P& a, const P& b){ return real(conj(a)*b); }  // 内積
double det(const P& a, const P& b){ return imag(conj(a)*b); }  // 外積

typedef vector<P> G;

int ccw(P a, P b, P c)
{
  b -= a; c -= a;
  if (det(b, c) > 0)     return +1;         // counter clockwise
  if (det(b, c) < 0)     return -1;         // clockwise
  if (dot(b, c) < 0)     return +2;         // c--a--b on line
  if (norm(b) < norm(c)) return -2;         // a--b--c on line  return 0;
}

vector<P> AndrewMonotoneChain(vector<P> ps)
{
  int n = ps.size(), k = 0;
  sort(ps.begin(), ps.end());
  vector<P> ch(2*n);
  for(int i=0; i<n; ch[k++]=ps[i++]) // lower-hull
    while(k >= 2 && ccw(ch[k-2], ch[k-1], ps[i]) <= 0) --k;
  for(int i=n-2, t=k+1; i>= 0; ch[k++]=ps[i--]) // upper-hull
    while(k >= t && ccw(ch[k-2], ch[k-1], ps[i]) <= 0) --k;
  ch.resize(k-1);
  return ch;
}

double Caliper(const vector<P>& v)
{
  int n = v.size();

  int si = 0;
  int sj = 0;
  rep(t, n){
    if(v[t].imag() < v[si].imag()) si = t;
    if(v[t].imag() > v[sj].imag()) sj = t;
  }

  double res = 0;
  int i = si;
  int j = sj;
  do{
    maxup(res, abs(v[i]-v[j]));
    P di = v[(i+1)%n] - v[i];
    P dj = v[(j+1)%n] - v[j];
    if(det(di, dj) >= 0) j = (j+1)%n;
    else i = (i+1)%n;
  }while(!(i == si && j == sj));

  return res;
}

const int MAX_N = 120000;
const double MAX_XY = 10000.0;
const int B = 50;
int n;
double x, y;
P z[MAX_N];
double res;
bool used[MAX_N];
vi bucket[2 * MAX_N / 10 / B][2 * MAX_N / 10 / B];

bool check(P z, P w){ return (z-w).real()*(z-w).real()+(z-w).imag()*(z-w).imag() <= 100.0; }
bool check(int x, int y){ return 0<=x && 0<=y; }

int main()
{
  cin >> n;

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

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

  rep(i, n){
    bucket[(int)(z[i].real()/B)][(int)(z[i].imag()/B)].pb(i);
  }

  vi g[MAX_N];
  rep(i, n) erep(dx, -1, 1) erep(dy, -1, 1){
    int nx = z[i].real() / B + dx;
    int ny = z[i].imag() / B + dy;
    if(!check(nx, ny)) continue;

    //    g[i].pb(i);
    vrep(v, bucket[nx][ny]){
      if(i != *v && check(z[i], z[*v])) g[i].pb(*v);
    }
  }

  rep(i, n) if(!used[i]){
    G ConvexHull;
    ConvexHull.pb(z[i]);

    queue<int> que;
    que.push(i);
    used[i] = true;
    while(!que.empty()){
      int top = que.front();
      que.pop();
      vrep(v, g[top]) if(!used[*v]){
        used[*v] = true;
        que.push(*v);
        ConvexHull.pb(z[*v]);
      }
    }

    if(ConvexHull.size() == 2) maxup(res, abs(ConvexHull[0] - ConvexHull[1]));
    if(ConvexHull.size() >  2){
      ConvexHull = AndrewMonotoneChain(ConvexHull);
      maxup(res, Caliper(ConvexHull));
    }
  }

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

  return 0;
}
0