結果

問題 No.96 圏外です。
ユーザー kyuridenamida
提出日時 2014-12-08 01:40:45
言語 C++11
(gcc 13.3.0)
結果
RE  
(最新)
AC  
(最初)
実行時間 -
コード長 2,508 bytes
コンパイル時間 1,748 ms
コンパイル使用メモリ 173,548 KB
実行使用メモリ 131,904 KB
最終ジャッジ日時 2024-12-24 07:55:06
合計ジャッジ時間 14,669 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 1 RE * 27
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int dfs(int)’:
main.cpp:72:1: warning: no return statement in function returning non-void [-Wreturn-type]
   72 | }
      | ^

ソースコード

diff #
プレゼンテーションモードにする

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
//と思ったら僕がバカでしたごめんなさいリバーシのルールを忘れていましたごめんなさい
const double INF = 1e12;
const double EPS = 1e-9;
typedef complex<double> P,point;
 
std::istream& operator>>(std::istream& is,P& p)
{
    double x,y;
    is >> x >> y;
    p = P(x,y);
    return is;
}
 
typedef vector<P> G,polygon;
namespace std {bool operator < (const P& a, const P& b) {return real(a) != real(b) ? real(a) < real(b) : imag(a) < imag(b);} }
double cross(const P& a, const P& b) {return imag(conj(a)*b);}
double dot(const P& a, const P& b) {return real(conj(a)*b);}
int ccw(P a, P b, P c) {
    b -= a; c -= a;
    if (cross(b, c) > 0)   return +1;
    if (cross(b, c) < 0)   return -1;
    if (dot(b, c) < 0) return +2;
    if (norm(b) < norm(c)) return -2;
    return 0;
}
vector<point> convex_hull(vector<point> ps) {
  int n = ps.size(), k = 0;
  sort(ps.begin(), ps.end());
  vector<point> 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;
}
vector<int> b[2020][2020];
P ps[120010];
int done[120020];
inline long long dist(P a,P b){
    P c = a-b;
    return c.real() * c.real() + c.imag()*c.imag();
}
vector<P> conv;
int dfs(int id){
    stack<int> S;
    S.push(id);
    while( S.size() ){
        id = S.top(); S.pop();
        if( done[id]++ ) continue;
        P p = ps[id];
        conv.push_back(p);
        int x = (int)p.real()/10;
        int y = (int)p.imag()/10;
        for(int i = -2 ; i <= 2 ; i++){
            for(int j = -2 ; j <= 2 ; j++){
                for( auto next : b[x+i][y+j] ){
                    if( dist(ps[next],p) <= 100 ){
                        S.push(next);
                    }
                }
            }
        }
    }
}
int main(){
    int N;
    cin >> N;
    if( N == 0 ){
        cout << 1.0 << endl;
        return 0;
    }
    for(int i = 0 ; i < N ; i++){
        P p;
        cin >> p;
        p += P(10050,10050);
        ps[i] = p;
        b[(int)p.real()/10][(int)p.imag()/10].push_back(i);
    }
    long long ans = 0;
    for(int i = 0 ; i < N ; i++){
        if( done[i] == 0 ){
            conv.clear();
            dfs(i);
            if( conv.size() >= 3 ){
                conv = convex_hull(conv);
            }
            for( int j = 0 ; j < conv.size() ; j++)
                for(int k = j+1 ; k < conv.size() ; k++)
                    ans = max(ans,dist(conv[j],conv[k]));
        }
    }
    printf("%.10lf\n",sqrt(ans)+2);
    
    
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0