結果

問題 No.96 圏外です。
ユーザー imgry22imgry22
提出日時 2015-01-24 18:42:03
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 3,724 bytes
コンパイル時間 1,446 ms
コンパイル使用メモリ 174,116 KB
実行使用メモリ 213,704 KB
最終ジャッジ日時 2024-06-23 01:18:39
合計ジャッジ時間 12,156 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 94 ms
141,568 KB
testcase_01 AC 102 ms
141,372 KB
testcase_02 AC 94 ms
141,524 KB
testcase_03 AC 92 ms
141,196 KB
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 AC 414 ms
162,852 KB
testcase_21 AC 295 ms
158,640 KB
testcase_22 AC 1,407 ms
213,700 KB
testcase_23 AC 1,468 ms
213,704 KB
testcase_24 AC 92 ms
141,568 KB
testcase_25 WA -
testcase_26 WA -
testcase_27 WA -
権限があれば一括ダウンロードができます
コンパイルメッセージ
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[MAX_N / B][MAX_N / B];

bool check(P z, P w){ return abs(z - w) <= 10; }
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) continue;
    if(ConvexHull.size() == 2) maxup(res, abs(z[0] - z[1]));
    if(ConvexHull.size() >  2){
      ConvexHull = AndrewMonotoneChain(ConvexHull);
      maxup(res, Caliper(ConvexHull));
    }
  }

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

  return 0;
}
0