結果
| 問題 |
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 °ree) { 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();
}