#1048004 (C++23) No.3042 拡大コピー

• 問題: No.3042 拡大コピー
• ユーザー: Katu2ou
• 提出日時: 2025-03-01 11:02:59
• 言語: C++23 (gcc 13.3.0 + boost 1.87.0)
• 結果: WA
• 実行時間: -
• コード長: 13,038 bytes
• コンパイル時間: 6,826 ms
• コンパイル使用メモリ: 334,276 KB
• 実行使用メモリ: 39,520 KB
• 最終ジャッジ日時: 2025-03-01 11:03:08
• 合計ジャッジ時間: 8,692 ms
• ジャッジサーバーID （参考情報）: judge3 / judge2

ファイルパターン	結果
sample	AC * 1
other	WA * 24

ソースコード

//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;

#define rep2(i, m, n) for (int i = (m); i < (n); ++i)
#define rep(i, n) rep2(i, 0, n)
#define drep2(i, m, n) for (int i = (m)-1; i >= (n); --i)
#define drep(i, n) drep2(i, n, 0)
#define all(...) std::begin(__VA_ARGS__), std::end(__VA_ARGS__)
#define rall(...) std::rbegin(__VA_ARGS__), std::rend(__VA_ARGS__)
#define CLR(a, b) memset((a), (b), sizeof(a))
#define DUMP(x) cout << #x << " = " << (x) << endl;
#define INF (long long)1001001001001001001
#define inf 1001001000
#define MOD 998244353
#define MOD1 1000000007
#define PI 3.14159265358979
#define epsilon 1e-12
#define fcout cout << fixed << setprecision(12)
#define MP make_pair
#define PB push_back
#define fi first
#define se second
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())

using ll = long long;
using ld = long double;
using vi = vector<int>;
using vl = vector<long long>;
using vs = vector<string>;
using vd = vector<double>;
using vld = vector<long double>;
using vb = vector<bool>;
using vpii = vector<pair<int, int>>;
using vpll = vector<pair<long long, long long>>;
using vvi = vector<vector<int>>;
using vvl = vector<vector<long long>>;
using vvd = vector<vector<double>>;
using vvld = vector<vector<long double>>;
using vvb = vector<vector<bool>>;
using vvpii = vector<vector<pair<int,int>>>;
using vvpll = vector<vector<pair<long long,long long>>>;
using vvvi = vector<vector<vector<int>>>;
using vvvl = vector<vector<vector<long long>>>;
using pii = pair<int, int>;
using pll = pair<long long, long long>;
using LL = __int128_t;
using mint = atcoder::modint998244353;
using vmint = vector<mint>;
using vvmint = vector<vector<mint>>;
using vvvmint = vector<vector<vector<mint>>>;

ll gcd(ll x, ll y) {if (x == 0) return y;	return gcd(y%x, x);} 
ll lcm(ll x, ll y) { __int128_t xx,yy; xx=x; yy=y; __int128_t ans=xx * yy / gcd(x, y); ll ans2=ans; return ans2; }
template<typename T>
T POW(T x, ll n){T ret=1;	while(n>0){		if(n&1) ret=ret*x;		x=x*x;		n>>=1;	}	return ret;}
template<typename T>
T modpow(T a, ll n, T p) {	if(n==0) return (T)1;  if (n == 1) return a % p;  if (n % 2 == 1) return (a * modpow(a, n - 1, p)) % p;  T t = modpow(a, n / 2, p);  return (t * t) % p;}
template<typename T>
T modinv(T a, T m) {	if(m==0)return (T)1;	T b = m, u = 1, v = 0;	while (b) {		T t = a / b;		a -= t * b; swap(a, b);		u -= t * v; swap(u, v);	}	u %= m;	if (u < 0) u += m;	return u;}
ll REM(ll a, ll b){ return (a % b + b) % b;}
ll QUO(ll a, ll b){ return (a - REM(a, b)) / b;}
/*
random_device rd;
mt19937 gen(rd());
uniform_int_distribution<> dist1(1, 100); [1,100]
int random_value = dist1(gen);
*/
/*
auto start = chrono::steady_clock::now(); //時間計測の開始
auto now = std::chrono::steady_clock::now(); //現在時刻と開始時刻の差を測定
double elapsed = std::chrono::duration<double>(now - start).count(); //時間をdouble型で取得
*/
/*
const int MAXCOMB=510000;
std::vector<mint> FAC(MAXCOMB), FINV(MAXCOMB), INV(MAXCOMB);
void COMinit() {FAC[0] = FAC[1] = 1;FINV[0] = FINV[1] = 1;INV[1] = 1;for (int i = 2; i < MAXCOMB; i++) {FAC[i] = FAC[i - 1] * i;INV[i] = mint(0) - INV[mint::mod() % i] * (mint::mod() / i);FINV[i] = FINV[i - 1] * INV[i];}}
mint COM(int n, int k) {if (n < k) return 0;if (n < 0 || k < 0) return 0;return FAC[n] * FINV[k] * FINV[n - k];}
*/

template <typename T> inline bool chmax(T &a, T b) { return ((a < b) ? (a = b, true) : (false));}
template <typename T> inline bool chmin(T &a, T b) { return ((a > b) ? (a = b, true) : (false));}
template <class T> T BS(vector<T> &vec, T key) {return lower_bound(vec.begin(), vec.end(), key) - vec.begin();}
template<class T> pair<T,T> RangeBS(vector<T> &vec, T lowv, T highv){auto itr_l = lower_bound(vec.begin(), vec.end(), lowv); auto itr_r = upper_bound(vec.begin(), vec.end(), highv); return make_pair(distance(vec.begin(), itr_l), distance(vec.begin(), itr_r)-1);}
void fail() { cout << "-1\n"; exit(0); } void no() { cout << "No\n"; exit(0); } void yes() { cout << "Yes\n"; exit(0); }
int dx[] = { 1,0,-1,0,1,1,-1,-1 }; int dy[] = { 0,1,0,-1,1,-1,1,-1};
bool range_in(int i, int j, int h, int w){ if(i<0 || j<0 || i>=h || j>=w) return false; return true;} 
int bitcount(int n){n=(n&0x55555555)+(n>>1&0x55555555); n=(n&0x33333333)+(n>>2&0x33333333); n=(n&0x0f0f0f0f)+(n>>4&0x0f0f0f0f); n=(n&0x00ff00ff)+(n>>8&0x00ff00ff); n=(n&0x0000ffff)+(n>>16&0x0000ffff); return n;}

template<typename T>
struct Edge{
    int from, to, index;
    T cost;
    Edge() : from(-1), to(-1), index(-1), cost(0) {}
    Edge(int _to) : from(-1), to(_to), index(-1), cost(0) {}
    Edge(int _to, T _cost) : from(-1), to(_to), index(-1), cost(_cost) {}
    Edge(int _from, int _to, int _index) : from(_from), to(_to), index(_index), cost(0) {}
    Edge(int _from, int _to, int _index, T _cost) 
        : from(_from), to(_to), index(_index), cost(_cost) {}
    bool operator<(const Edge<T>& other) const {
        return cost < other.cost; 
    }
    Edge &operator=(const int &x) {
        to = x;
        return *this;
    }
    operator int() const { return to; }
};
using Graph = vector<vector<int>>; 
template <typename T>
using WGraph = vector<vector<Edge<T>>>; 

//////////////////////////////////////////////////////////////////////////////////////////

using Point = complex<long double>;
typedef Point pt;
const long double EPS = 1e-10;

inline bool equal(const long double &a, const long double &b) {
    return fabs(a - b) < EPS;
}

// 単位ベクトル(unit vector)を求める
Point unitVector(const Point &a) { return a / abs(a); }

// 法線ベクトル(normal vector)を求める
// 90度回転した単位ベクトルをかける
// -90度がよければPoint(0, -1)をかける
Point normalVector(const Point &a) { return a * Point(0, 1); }

// 内積(dot product) : a・b = |a||b|cosΘ
long double dot(const Point &a, const Point &b) {
    return (a.real() * b.real() + a.imag() * b.imag());
}

// 外積(cross product) : a×b = |a||b|sinΘ
long double cross(const Point &a, const Point &b) {
    return (a.real() * b.imag() - a.imag() * b.real());
}

// 点pを反時計回りにtheta度回転
Point rotate(const Point &p, const long double &theta) {
    return Point(cos(theta) * p.real() - sin(theta) * p.imag(),
                 sin(theta) * p.real() + cos(theta) * p.imag());
}    

// ラジアン->度
long double radianToDegree(const long double &radian) { return radian * 180.0 / PI; }

// 度->ラジアン
long double degreeToRadian(const long double &degree) { return degree * PI / 180.0; }

// Line : 直線を表す構造体
// b - a で直線・線分を表せる
struct Line {
    Point a, b;
    Line() = default;
    Line(Point a, Point b) : a(a), b(b) {}
    // Ax+By=C
    Line(long double A, long double B, long double C) {
        if(equal(A, 0)) {
            a = Point(0, C / B), b = Point(1, C / B);
        } else if(equal(B, 0)) {
            b = Point(C / A, 0), b = Point(C / A, 1);
        } else {
            a = Point(0, C / B), b = Point(C / A, 0);
        }
    }
};

// Segment : 線分を表す構造体
// Lineと同じ
struct Segment : Line {
    Segment() = default;

    Segment(Point a, Point b) : Line(a, b) {}
};

// Circle : 円を表す構造体
// pが中心の位置ベクトル、rは半径
struct Circle {
    Point p;
    long double r;

    Circle() = default;

    Circle(Point p, long double r) : p(p), r(r) {}
};

// 射影(projection)
// 直線(線分)lに点pから引いた垂線の足を求める
Point projection(const Line &l, const Point &p) {
    long double t = dot(p - l.a, l.a - l.b) / norm(l.a - l.b);
    return l.a + (l.a - l.b) * t;
}

Point projection(const Segment &l, const Point &p) {
    long double t = dot(p - l.a, l.a - l.b) / norm(l.a - l.b);
    return l.a + (l.a - l.b) * t;
}

// 反射(reflection)
// 直線lを対称軸として点pと線対称の位置にある点を求める
Point reflection(const Line &l, const Point &p) {
    return p + (projection(l, p) - p) * (long double)2.0;
}

// 点の回転方向
// 点a, b, cの位置関係について(aが基準点)
int ccw(const Point &a, Point b, Point c) {
    b -= a, c -= a;
    // 点a, b, c が
    // 反時計回りの時、
    if(cross(b, c) > EPS) {
        return 1;
    }
    // 時計回りの時、
    if(cross(b, c) < -EPS) {
        return -1;
    }
    // c, a, bがこの順番で同一直線上にある時、
    if(dot(b, c) < 0) {
        return 2;
    }
    // a, b, cがこの順番で同一直線上にある場合、
    if(norm(b) < norm(c)) {
        return -2;
    }
    // cが線分ab上にある場合、
    return 0;
}

// 2直線の直交判定 : a⊥b <=> dot(a, b) = 0
bool isOrthogonal(const Line &a, const Line &b) {
    return equal(dot(a.b - a.a, b.b - b.a), 0);
}
// 2直線の平行判定 : a//b <=> cross(a, b) = 0
bool isParallel(const Line &a, const Line &b) {
    return equal(cross(a.b - a.a, b.b - b.a), 0);
}

// 線分sと線分tが交差しているかどうか
bool isIntersect(const Segment &s, const Segment &t) {
    return ccw(s.a, s.b, t.a) * ccw(s.a, s.b, t.b) <= 0 &&
           ccw(t.a, t.b, s.a) * ccw(t.a, t.b, s.b) <= 0;
}

// 直線s, tの交点の計算
Point crossPoint(const Line &s, const Line &t) {
    long double d1 = cross(s.b - s.a, t.b - t.a);
    long double d2 = cross(s.b - s.a, s.b - t.a);
    if(equal(abs(d1), 0) && equal(abs(d2), 0)) {
        return t.a;
    }
    return t.a + (t.b - t.a) * (d2 / d1);
}

// 線分s, tの交点の計算
Point crossPoint(const Segment &s, const Segment &t) {
    return crossPoint(Line(s), Line(t));
}

// 線分lと点pの距離を求める
// 定義：点pから「線分lのどこか」への最短距離
long double distanceBetweenSegmentAndPoint(const Segment &l, const Point &p) {
    if(dot(l.b - l.a, p - l.a) < EPS) {
        return abs(p - l.a);
    }
    if(dot(l.a - l.b, p - l.b) < EPS) {
        return abs(p - l.b);
    }
    return abs(cross(l.b - l.a, p - l.a)) / abs(l.b - l.a);
}

// 線分sとtの距離
long double distanceBetweenSegments(const Segment &s, const Segment &t) {
    if(isIntersect(s, t)) {
        return (long double)(0);
    }
    long double ans = distanceBetweenSegmentAndPoint(s, t.a);
    chmin(ans, distanceBetweenSegmentAndPoint(s, t.b));
    chmin(ans, distanceBetweenSegmentAndPoint(t, s.a));
    chmin(ans, distanceBetweenSegmentAndPoint(t, s.b));
    return ans;
}

// 多角形の面積を求める
long double PolygonArea(const vector<Point> &p) {
    long double res = 0;
    int n = p.size();
    for(int i = 0; i < n - 1; i++) {
        res += cross(p[i], p[i + 1]);
    }
    res += cross(p[n - 1], p[0]);
    return res * 0.5;
}

// 凸多角形かどうか
bool isConvex(const vector<Point> &p) {
    int n = p.size();
    int now, pre, nxt;
    for(int i = 0; i < n; i++) {
        pre = (i - 1 + n) % n;
        nxt = (i + 1) % n;
        now = i;
        if(ccw(p[pre], p[now], p[nxt]) == -1) {
            return false;
        }
    }
    return true;
}

// 多角形gに点pが含まれているか?
// 含まれる:2, 辺上にある:1, 含まれない:0
int isContained(const vector<Point> &g, const Point &p) {
    bool in = false;
    int n = (int)g.size();
    for(int i = 0; i < n; i++) {
        Point a = g[i] - p, b = g[(i + 1) % n] - p;
        if(imag(a) > imag(b)) {
            swap(a, b);
        }
        if(imag(a) <= EPS && EPS < imag(b) && cross(a, b) < -EPS) {
            in = !in;
        }
        if(cross(a, b) == 0 && dot(a, b) <= 0) {
            return 1;
        }
    }
    return (in ? 2 : 0);
}

vector<Point> ConvexHull(vector<Point> &p) {
    int n = (int)p.size(), k = 0;
    sort(all(p), [](const Point &a, const Point &b) {
        return (real(a) != real(b) ? real(a) < real(b) : imag(a) < imag(b));
    });
    vector<Point> ch(2 * n);
    // 一直線上の3点を含める -> (< -EPS)
    // 含めない -> (< EPS)
    for(int i = 0; i < n; ch[k++] = p[i++]) { // lower
        while(k >= 2 && cross(ch[k - 1] - ch[k - 2], p[i] - ch[k - 1]) < EPS)
            --k;
    }
    for(int i = n - 2, t = k + 1; i >= 0; ch[k++] = p[i--]) { // upper
        while(k >= t && cross(ch[k - 1] - ch[k - 2], p[i] - ch[k - 1]) < EPS)
            --k;
    }
    ch.resize(k - 1);
    return ch;
}


void solve(){
    int n;
    cin>>n;
    vector<pt> p1(n);
    vector<pt> p2(n);
    rep(i,n){
        int a,b;
        cin>>a>>b;
        p1[i] = Point(a,b);
    }
    rep(i,n){
        int a,b;
        cin>>a>>b;
        p2[i] = Point(a,b);
    }
    p1 = ConvexHull(p1);
    p2 = ConvexHull(p2);
    long double d1 = 0;
    long double d2 = 0;
    rep(i,p1.size()-1){
        d1+=abs(p1[i+1]-p1[i]);
    }
    d1+=abs(p1[p1.size()-1]-p1[0]);
    rep(i,p2.size()-1){
        d2+=abs(p2[i+1]-p2[i]);
    }
    d2+=abs(p2[p2.size()-1]-p2[0]);
    cout<<d2/d1<<endl;
}

signed main(){
	ios::sync_with_stdio(0);
	cout<<fixed<<setprecision(20);
	int TT; TT = 1; //cin >> TT;
	while(TT--) solve();
}