結果

問題 No.3042 拡大コピー
ユーザー umezo
提出日時 2025-03-04 06:59:45
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 2,782 bytes
コンパイル時間 3,713 ms
コンパイル使用メモリ 287,396 KB
実行使用メモリ 22,440 KB
最終ジャッジ日時 2025-03-04 06:59:56
合計ジャッジ時間 10,957 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 1
other TLE * 1 -- * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define ALL(v) v.begin(), v.end()
typedef long long ll;

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

static const int COUNTER_CLOCKWISE=1;
static const int CLOCKWISE=-1;
static const int ONLINE_BACK=2;
static const int ONLINE_FRONT=-2;
static const int ON_SEGMENT=0;

class Point{
  public:
  double x,y;
  
  Point(ll x=0, ll y=0): x(x),y(y) {}
  
  Point operator+(Point p){return Point(x+p.x,y+p.y);}
  Point operator-(Point p){return Point(x-p.x,y-p.y);}
  Point operator*(ll a){return Point(a*x,a*y);}
  Point operator/(ll a){return Point(x/a,y/a);}
  
  bool operator<(const Point &p) const{
    return x != p.x ? x<p.x : y<p.y;
  }
  
  bool operator==(const Point &p) const{
    return x==p.x && y==p.y;
  }
};
typedef Point Vector;
typedef vector<Point> Polygon;
double dot(Vector a,Vector b){return a.x*b.x+a.y*b.y;}
double cross(Vector a,Vector b){return a.x*b.y-a.y*b.x;}
int ccw(Point p0,Point p1,Point p2){
  Vector a=p1-p0;
  Vector b=p2-p0;
  if(cross(a,b)>0) return COUNTER_CLOCKWISE;
  if(cross(a,b)<0) return CLOCKWISE;
  return ON_SEGMENT;
}

Polygon andrewScan(Polygon s){
  Polygon u,l;
  if(s.size()<3) return s;
  sort(ALL(s));
  u.push_back(s[0]);
  u.push_back(s[1]);
  l.push_back(s[s.size()-1]);
  l.push_back(s[s.size()-2]);
  for(int i=2;i<(int)s.size();i++){
    for(int j=(int)u.size();j>=2 && ccw(u[j-2],u[j-1],s[i])==COUNTER_CLOCKWISE;j--){
      u.pop_back();
    }
    u.push_back(s[i]);
  }
  for(int i=(int)s.size()-3;i>=0;i--){
    for(int j=(int)l.size();j>=2 && ccw(l[j-2],l[j-1],s[i])==COUNTER_CLOCKWISE;j--){
      l.pop_back();
    }
    l.push_back(s[i]);
  }
  reverse(ALL(l));
  for(int i=(int)u.size()-2;i>=1;i--) l.push_back(u[i]);
  return l;
}

//最遠点対間距離（キャリパー法）
bool cmp_x(const Point& p,const Point& q){
  if(p.x!=q.x) return p.x<q.x;
  return p.y<q.y;
}
double dist(Point p,Point q){return sqrt(dot(p-q,p-q));}
double calipers(Polygon &p){
  int n=p.size();
  if(n==2) return dist(p[0],p[1]);
  int i=0,j=0;
  for(int k=0;k<n;k++){
    if(!cmp_x(p[i],p[k])) i=k;
    if(cmp_x(p[j],p[k])) j=k;
  }
  double res=0;
  int si=i,sj=j;
  while(i!=sj || j!=si){
    res=max(res,dist(p[i],p[j]));
    if(cross(p[(i+1)%n]-p[i],p[(j+1)%n]-p[j])<0) i=(i+1)%n;
    else j=(j+1)%n;
  }
  return res;
}
//

int main(){
  ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  
  int n;
  cin>>n;
  Polygon p,q;
  rep(i,n){
    double x,y;
    cin>>x>>y;
    p.push_back(Point(x,y));
  }
  Polygon tmp1=andrewScan(p);
  double ans1=calipers(tmp1);
  
  rep(i,n){
    double x,y;
    cin>>x>>y;
    q.push_back(Point(x,y));
  }
  Polygon tmp2=andrewScan(q);
  double ans2=calipers(tmp2);
  
  cout<<fixed<<setprecision(10)<<ans2/ans1<<endl;
  
  return 0;
}
0