#148547 (C++14) No.96 圏外です。

提出ソース
結果

問題	No.96 圏外です。
コンテスト
ユーザー	r_dream0
提出日時	2017-02-09 17:06:10
言語	C++14 (gcc 13.3.0 + boost 1.87.0)
結果	AC
実行時間	394 ms / 5,000 ms
コード長	13,699 bytes
コンパイル時間	2,343 ms
コンパイル使用メモリ	135,740 KB
実行使用メモリ	30,024 KB
最終ジャッジ日時	2024-12-26 02:04:59
合計ジャッジ時間	8,669 ms
ジャッジサーバーID （参考情報）	judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン	結果
other	AC * 28
権限があれば一括ダウンロードができます
ソースコード

raw source code
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <climits>
#include <queue>
#include <stack>
#include <algorithm>
#include <list>
#include <vector>
#include <set>
#include <map>
#include <iostream>
#include <deque>
#include <complex>
#include <string>
#include <iomanip>
#include <sstream>
#include <bitset>
#include <valarray>
#include <iterator>
using namespace std;

typedef long long int lli;
typedef unsigned int uint;
typedef unsigned char uchar;
typedef unsigned long long ull;

#define REP(i,x) for(int i=0;i<(int)(x);i++)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();i++)
#define RREP(i,x) for(int i=(x);i>=0;i--)
#define RFOR(i,c) for(__typeof((c).rbegin())i=(c).rbegin();i!=(c).rend();i++)

const double EPS=1e-5;
const double INF=1e10;

const double PI = M_PI;
// 平面上の点
struct Point{
  Point(double x, double y):x(x) ,y(y){}
  Point(){}
  double x,y;
};
Point operator+(const Point &a, const Point &b){
  return Point(a.x + b.x, a.y + b.y);
}
Point operator-(const Point &a, const Point &b){
  return Point(a.x - b.x, a.y - b.y);
}
Point operator*(const Point &a, const double b){
  return Point(a.x * b, a.y * b);
}
// 必要時定義(複素数の積)
Point operator*(const Point &a,const Point &b){
  return Point(a.x*b.x-a.y*b.y, a.x*b.y+a.y*b.x);
}
// 必要時定義 (基本的に * 1.0 / (ほげほげ)で済ます
Point operator/(const Point &a, const double b){
  return Point(a.x / b, a.y / b);
}
// 外積 a × b
double cross(const Point &a, const Point &b){
  return a.x * b.y - a.y * b.x;
}
// 内積 a ・ b
double dot(const Point &a, const Point &b){
  return a.x * b.x + a.y * b.y;
}
// 比較 (必要時のみ定義)
bool operator<(const Point &a, const Point &b){
  return make_pair(a.x, a.y) < make_pair(b.x, b.y);
}
// 角度(必要時のみ定義)
double atan(const Point &a){
  return atan2(a.y, a.x);
}
// |a|^2
double norm(const Point &a){
  return dot(a, a);
}
// |a|
double abs(const Point &a){
  return sqrt(norm(a));
}

// 点の90度回転(必要時定義)
Point rotate90(const Point &a){
  return Point(-a.y, a.x);
}
// 点の回転(必要時定義) ラジアン注意
Point rotate(const Point &a, double angle){
  return Point(cos(angle) * a.x - sin(angle) * a.y, sin(angle) * a.x + cos(angle) * a.y);
}
// 直線・線分
struct Line:vector<Point>{
  Line(Point a = Point(0,0), Point b = Point(0,0)){
    this->push_back(a);
    this->push_back(b);
  }
};

// 円
struct Circle: Point{
  double r;
  Circle(Point p = Point(0,0), double r=0):Point(p),r(r){}
};

// 多角形
typedef vector<Point> Polygon;

// 前後の頂点情報(必要時のみ)
Point next(const Polygon &a, int x){
  return a[(x + 1) % a.size()];
}
Point prev(const Polygon &a, int x){
  return a[(x - 1 + a.size()) % a.size()];
}

ostream& operator<<(ostream &os, const Point &a){
  return os<<"("<<a.x<<","<<a.y<<")";
}

istream& operator>>(istream &is, Point &a){
  return is>>a.x>>a.y;
}

int ccw(Point a, Point b, Point c){
  b = b - a; c = c - a;
  if (cross(b, c) > EPS) return +1; // 反時計周り
  if (cross(b, c) < -EPS) return -1;// 時計周り
  if (dot(b, c) < 0) return +2;     // c--a--bがこの順番に一直線上
  if (norm(b) < norm(c)) return -2; // a--b--cがこの順番に一直線上
  return 0;                         // a--c--bが一直線上
}
// 直線交差判定
// 同一直線の場合は交差していると判定する。
bool is_intersect_LL(const Line &l, const Line &m){
  return abs(cross(l[1] - l[0], m[1] - m[0])) > EPS || // 傾きが異なる
    abs(cross(l[1] - l[0], m[1] - l[0])) < EPS; // 同じ直線である
}

// 直線と線分の交差判定
// 同一直線上にある場合も交差と判定
bool is_intersect_LS(const Line &l, const Line &s){
  return cross(l[1] - l[0], s[0] - l[0]) *
    cross(l[1] - l[0], s[1] - l[0]) < EPS;
}

// 直線が線分を含むかの判定
bool is_intersect_LP(const Line &l, const Point &p){
  return abs(ccw(l[0], l[1], p))!=1;
}

// 線分交差判定
bool is_intersect_SS(const Line &s, const Line &t){
  return ccw(s[0], s[1], t[0]) * ccw(s[0], s[1], t[1]) <= 0 &&
    ccw(t[0], t[1], s[0]) * ccw(t[0], t[1], s[1]) <= 0;
}

// 線分が直線を含むかどうか
bool is_intersect_SP(const Line &l, const Point &p){
  return ccw(l[0], l[1], p) == 0;
}

// 円が点を含むかどうか(境界含む EPSに注意)
bool is_intersect_CP(const Circle &c, const Point &p){
  return abs(c-p)<=c.r+EPS;
}

// 2円が共有点を持つかどうか (EPSに注意)
bool is_intersect_CC(const Circle &c,const Circle &d){
  return abs(c-d)<=c.r+d.r &&
    abs(c-d)>= abs(c.r-d.r);
}
// 写像
Point projection(const Line &l, const Point &p){
  double t = dot(p - l[0], l[1] - l[0]) / norm(l[0] - l[1]);
  return l[0] + (l[1] - l[0]) * t;
}

// 反射
Point reflection(const Line &l, const Point &p){
  return p + (projection(l, p) - p) * 2;
}

// 直線と点の距離
double distance_LP(const Line &l, const Point &p){
  return abs(p - projection(l, p));
}

// 直線と直線の距離
double distance_LL(const Line &l, const Line &m){
  return is_intersect_LL(l, m) ? 0 : distance_LP(l, m[0]);
}

// 直線と線分の距離
double distance_LS(const Line &l, const Line &s){
  if(is_intersect_LS(l, s)) return 0;
  return min(distance_LP(l, s[0]),distance_LP(l, s[1]));
}

// 線分と点の距離
double distance_SP(const Line &s, const Point &p){
  const Point r = projection(s, p);
  if(is_intersect_SP(s, r))return abs(r - p);
  return min(abs(s[0] - p), abs(s[1] - p));
}
// 線分同士の距離
double distance_SS(const Line &s, const Line &t){
  if(is_intersect_SS(s, t)) return 0;
  return min(min(distance_SP(s, t[0]), distance_SP(s, t[1])),
      min(distance_SP(t, s[0]), distance_SP(t, s[1])));
}

// 直線の交点
Point crosspoint_LL(const Line &l,const Line &m){
  double d = cross(m[1] - m[0], l[1] - l[0]);
  if(abs(d) < EPS) throw "線分が平行です"; // 線分が平行。場合によってはl[0]を返すようにする
  return l[0] + (l[1] - l[0]) * cross(m[1] - m[0], m[1] - l[0]) * (1.0 / d);
}
// 2円の交点
vector<Point> crosspoint_CC(const Circle &c1,const Circle &c2){
  vector<Point> res;
  if(abs(c1-c2)<EPS)return vector<Point>(); // 交点が絶対にない
  double d=abs(c1-c2);
  double rc=(d*d+c1.r*c1.r-c2.r*c2.r)/(2*d);
  double rs=sqrt(c1.r*c1.r-rc*rc);
  Point diff = (c2 - c1)/d;
  res.push_back(Point(c1 + diff * Point(rc,rs)));
  res.push_back(Point(c1 + diff * Point(rc,-rs)));
  return res;
}
// 円と線分の直線
vector<Point> crosspoint_CL(const Circle &a,const Line &b){
  vector<Point> res;
  double dist=distance_LP(b,a);
  if(dist<=a.r){
    Point s=projection(b,a);
    dist=sqrt(a.r*a.r-dist*dist);
    Point t=(b[1]-b[0])/abs(b[1]-b[0]);
    res.push_back(s+t*dist);
    res.push_back(s-t*dist);
  }
  return res;
}
// 点pから引いた円の接点
vector<Point> tangentCP(const Circle &c, const Point &p){
  double x = norm(p - c);
  double d = x - c.r * c.r;
  if(d < -EPS) return vector<Point>();
  d = max(d, 0.0);
  Point q1 = (p - c) * (c.r * c.r / x);
  Point q2 = rotate90((p - c) * (-c.r * sqrt(d) / x));
  vector<Point> ret;
  ret.push_back(c + q1 - q2);
  ret.push_back(c + q1 + q2);
  return ret;
}
// 2円の共通接線を求める
vector<Line> tangentCC(const Circle &a, const Circle &b){
  vector<Line> list;
  // 外接線の計算
  if(abs(a.r - b.r) < EPS){ // 2円の半径が同じ
    Point dir = b - a;
    dir = rotate90(dir * (a.r / abs(dir)));
    list.push_back(Line(a + dir, b + dir));
    list.push_back(Line(a - dir, b - dir));
  } else {
    Point p = (a * (-b.r)) + (b * a.r);
    p = p * (1 / (a.r - b.r));
    vector<Point> ps = tangentCP(a, p);
    vector<Point> qs = tangentCP(b, p);
    REP(i, min(ps.size(),qs.size())){
      list.push_back(Line(ps[i],qs[i]));
    }
  }
  // 内接線の計算
  Point p = (a * b.r) + (b * a.r);
  p = p * (1 / (a.r + b.r));
  vector<Point> ps = tangentCP(a, p);
  vector<Point> qs = tangentCP(b, p);
  REP(i, min(ps.size(),qs.size())){
    list.push_back(Line(ps[i],qs[i]));
  }
  return list;
}
double area(const Polygon &a){
  double ret = 0.0;
  REP(i, a.size()){
    ret += cross(a[i], next(a, i));
  }
  return abs(ret) * .5;
}
// 多角形の重心を求める
Point center_of_gravity(const Polygon &P){
  Point p;
  REP(i, P.size())p=p+P[i];
  return p*(1.0/P.size());
}
pair<Point,double> smallest_enclosing_circle(const vector<Point> &pts){
  Point p(0,0);
  REP(i,pts.size())p = p + pts[i];
  p = p * (1. / pts.size()); // 初期の点を重心にする
  double d = 0.5;
  // ステップ数を増やすと精度が良くなる
  for(int k = 1; k <= 30; k++){
    for(int i = 0; i < 10 ; i++){
      int s = 0;
      REP(i, pts.size()){
        if(abs(pts[i] - p) > abs(pts[s] - p)){
          s = i;
        }
      }
      p = p + (pts[s] - p) * d;
    }
    d *= 0.5;
  }
  double max_dist = 0;
  REP(i, pts.size()){
    if(abs(pts[i] - p) > max_dist){
      max_dist = abs(pts[i] - p);
    }
  }
  return make_pair(p, max_dist);
}
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;
}

/* 扇型 */
struct Sector : public Circle{
  double angle; // 開始角度(ラジアン)
  double size; // 角度の大きさ(ラジアン)
  Sector(Point p=Point(0,0),double r=0,double a=0,double l=0):
    Circle(p,r), angle(a), size(l)
  {}
};

// 点が扇型に含まれるかどうか
bool is_intersect_SecP(const Sector &sec,const Point &p){
  if(!is_intersect_CP(sec, p))return false;
  if(abs(p-sec)<EPS)return true;
  double a = atan(p - sec); //点の方向を求める
  for(int i=-4;i<=4;i+=2){
    if(sec.angle+i*PI - EPS <= a && a <= EPS + sec.angle + i * PI + sec.size){
      return true;
    }
  }
  return false;
}

// ax+by+c=0 と Ax^2 + Bxy + Cy^2 + Dx + Ey + C = 0の交点を求める
vector<Point> crosspoint_LQ(double a,double b,double c,double A,double B,double C,double D,double E,double F){
  if(b==0){
    vector<Point> ret=crosspoint_LQ(b,a,c,C,B,A,E,D,F);
    REP(i,ret.size()){
      ret[i]=Point(ret[i].y,ret[i].x);
    }
    return ret;
  }
  double P=A*b*b-B*b*a+C*a*a;
  double Q=-B*b*c+2*C*a*c+D*b*b-E*a*b;
  double R=C*c*c-E*b*c+F*b*b;
  if(P==0){
    double x=-R/Q;
    vector<Point> ret;
    ret.push_back(Point(x,(-a*x-c)/b));
    return ret;
  }else{
    double d=Q*Q-4*P*R;
    vector<Point> ret;
    if(d==0){
      double x=-Q/(2*P);
      ret.push_back(Point(x,(-a*x-c)/b));
    }else if(d>0){
      double x=(-Q-sqrt(d))/(2*P);
      ret.push_back(Point(x,(-a*x-c)/b));
      x=(-Q+sqrt(d))/(2*P);
      ret.push_back(Point(x,(-a*x-c)/b));
    }
    return ret;
  }
}
struct UnionFind{
  vector<int> par;vector<int> rank;
  UnionFind(int n){
    par=vector<int>(n);rank=vector<int>(n);
    for(int i=0;i<n;i++){
      par[i]=i;
    }
  }
  int find(int x){
    if(par[x]==x)
      return x;
    else
      return par[x] = find(par[x]);
  }
  void unite(int x,int y){
    x=find(x);y=find(y);
    if(x==y)return;
    if(rank[x]<rank[y]){
      par[x]=y;
    } else{
      par[y]=x;
      if(rank[x]==rank[y]) rank[x]++;
    }
  }
  inline bool same(int x,int y){
    return find(x)==find(y);
  }
};
int64_t N;
vector<int> X, Y;
const int MAX_X = 20001;
const int SPLIT_X = 200;
int MAP[SPLIT_X][MAX_X];

vector<int> dx, dy;
void init() {
  for(int x = -10; x <= 10; x++) {
    for(int y = -10; y <= 10; y++) {
      if((x | y ) == 0) continue;
      if(x * x + y * y <= 100) {
        dx.push_back(x);
        dy.push_back(y);
      }
    }
  }
  memset(MAP, -1, sizeof(MAP));
}
int main() {
  init();
  cin >> N;
  X = vector<int>(N);
  Y = vector<int>(N);
  vector<pair<int,int >> pts[MAX_X];
  for(int i = 0; i < N; i++) {
    cin >> X[i] >> Y[i];
    X[i] += 10000;
    Y[i] += 10000;
    pts[X[i]].emplace_back(Y[i], i);
  }
  for(int x = 0; x <= 10; x++) {
    for(int i = 0; i < pts[x].size(); i++) {
      MAP[x][pts[x][i].first] = pts[x][i].second;
    }
  }
  UnionFind uf(N);
  for(int x = 0; x < MAX_X; x++) {
    for(int i = 0; i < pts[x].size(); i++) {
      int y = pts[x][i].first, pno = pts[x][i].second;
      for(int k = 0; k < dx.size(); k++) {
        int nx = x + dx[k], ny = y + dy[k];
        if(nx < 0 || ny < 0 || nx >= MAX_X || ny >= MAX_X) continue;
        if(MAP[nx % SPLIT_X][ny] != -1) {
          int to = MAP[nx % SPLIT_X][ny];
          uf.unite(pno, to);
        }
      }
    }
    // 更新
    if(x - 10 >= 0) {
      for(int i = 0; i < pts[x - 10].size(); i++) {
        int y = pts[x - 10][i].first;
        MAP[(x - 10) % SPLIT_X][y] = -1;
      }
    }
    if(x + 11 < MAX_X) {
      for(int i = 0; i < pts[x + 11].size(); i++) {
        int y = pts[x + 11][i].first;
        MAP[(x + 11) % SPLIT_X][y] = pts[x + 11][i].second;
      }
    }
  }
  // UnionFind木を使っていろいろやる
  vector<vector<int> > pt_grp(N);
  for(int i = 0; i < N; i++) {
    pt_grp[uf.find(i)].push_back(i);
  }
  double ans = 2;
  if(N == 0) ans = 1;
  for(int i = 0; i < N; i++) {
    if(pt_grp[i].size() <= 1) continue;
    vector<Point> points;
    for(int k: pt_grp[i]) {
      points.push_back(Point(X[k], Y[k]));
    }
    points = convex_hull(points);
    for(int i = 0; i < points.size(); i++) {
      for(int j = 0; j < i; j++) {
        ans = max(ans, 2 + abs(points[i] - points[j]));
      }
    }
  }
  cout << setprecision(20) << ans <<  endl;
}
yukicoder

結果

ソースコード
