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

提出ソース
結果

問題	No.3042 拡大コピー
コンテスト
ユーザー	Aeren
提出日時	2025-02-28 22:15:40
言語	C++23 (gcc 13.3.0 + boost 1.87.0)
結果	RE
実行時間	-
コード長	12,533 bytes
コンパイル時間	3,640 ms
コンパイル使用メモリ	291,028 KB
実行使用メモリ	11,184 KB
最終ジャッジ日時	2025-03-01 07:39:02
合計ジャッジ時間	7,599 ms
ジャッジサーバーID （参考情報）	judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン	結果
sample	AC * 1
other	RE * 24
権限があれば一括ダウンロードができます
ソースコード

raw source code
// #include <bits/allocator.h> // Temp fix for gcc13 global pragma
// #pragma GCC target("avx2,bmi2,popcnt,lzcnt")
// #pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
// #include <x86intrin.h>
using namespace std;
#if __cplusplus >= 202002L
using namespace numbers;
#endif
#ifdef LOCAL
	#include "Debug.h"
#else
	#define debug_endl() 42
	#define debug(...) 42
	#define debug2(...) 42
	#define debugbin(...) 42
#endif

template<class T>
struct point{
	T x{}, y{};
	point(){ }
	template<class U> point(const point<U> &otr): x(otr.x), y(otr.y){ }
	template<class U, class V> point(U x, V y): x(x), y(y){ }
	template<class U> point(const array<U, 2> &p): x(p[0]), y(p[1]){ }
	friend istream &operator>>(istream &in, point &p){
		return in >> p.x >> p.y;
	}
	friend ostream &operator<<(ostream &out, const point &p){
		return out << "{" << p.x << ", " << p.y << "}";
	}
	template<class U> operator array<U, 2>() const{
		return {x, y};
	}
	T operator*(const point &otr) const{
		return x * otr.x + y * otr.y;
	}
	T operator^(const point &otr) const{
		return x * otr.y - y * otr.x;
	}
	point operator+(const point &otr) const{
		return {x + otr.x, y + otr.y};
	}
	point &operator+=(const point &otr){
		return *this = *this + otr;
	}
	point operator-(const point &otr) const{
		return {x - otr.x, y - otr.y};
	}
	point &operator-=(const point &otr){
		return *this = *this - otr;
	}
	point operator-() const{
		return {-x, -y};
	}
#define scalarop_l(op) friend point operator op(const T &c, const point &p){ return {c op p.x, c op p.y}; }
	scalarop_l(+) scalarop_l(-) scalarop_l(*) scalarop_l(/)
#define scalarop_r(op) point operator op(const T &c) const{ return {x op c, y op c}; }
	scalarop_r(+) scalarop_r(-) scalarop_r(*) scalarop_r(/)
#define scalarapply(applyop, op) point &operator applyop(const T &c){ return *this = *this op c; }
	scalarapply(+=, +) scalarapply(-=, -) scalarapply(*=, *) scalarapply(/=, /)
#define compareop(op) bool operator op(const point &otr) const{ return pair<T, T>(x, y) op pair<T, T>(otr.x, otr.y); }
	compareop(>) compareop(<) compareop(>=) compareop(<=) compareop(==) compareop(!=)
#undef scalarop_l
#undef scalarop_r
#undef scalarapply
#undef compareop
	double norm() const{
		return sqrt(x * x + y * y);
	}
	long double norm_l() const{
		return sqrtl(x * x + y * y);
	}
	T squared_norm() const{
		return x * x + y * y;
	}
	// [0, 2 * pi]
	double angle() const{
		auto a = atan2(y, x);
		if(a < 0) a += 2 * acos(-1);
		return a;
	}
	// [0, 2 * pi]
	long double angle_l() const{
		auto a = atan2(y, x);
		if(a < 0) a += 2 * acosl(-1);
		return a;
	}
	point<double> unit() const{
		return point<double>(x, y) / norm();
	}
	point<long double> unit_l() const{
		return point<long double>(x, y) / norm_l();
	}
	point perp() const{
		return {-y, x};
	}
	point<double> normal() const{
		return perp().unit();
	}
	point<long double> normal_l() const{
		return perp().unit_l();
	}
	point<double> rotate(double theta) const{
		return {x * cos(theta) - y * sin(theta), x * sin(theta) + y * cos(theta)};
	}
	point<long double> rotate_l(double theta) const{
		return {x * cosl(theta) - y * sinl(theta), x * sinl(theta) + y * cosl(theta)};
	}
	point reflect_x() const{
		return {x, -y};
	}
	point reflect_y() const{
		return {-x, y};
	}
	point reflect(const point &o = {}) const{
		return {2 * o.x - x, 2 * o.y - y};
	}
	bool parallel_to(const point &q) const{
		if constexpr(is_floating_point_v<T>) return abs(*this ^ q) <= 1e-9;
		else return abs(*this ^ q) == 0;
	}
};
template<class T, class U>
point<double> lerp(const point<T> &p, const point<U> &q, double t){
	return point<double>(p) * (1 - t) + point<double>(q) * t;
}
template<class T, class U>
point<long double> lerp_l(const point<T> &p, const point<U> &q, long double t){
	return point<long double>(p) * (1 - t) + point<long double>(q) * t;
}
template<class T>
double distance(const point<T> &p, const point<T> &q){
	return (p - q).norm();
}
template<class T>
long double distance_l(const point<T> &p, const point<T> &q){
	return (p - q).norm_l();
}
template<class T>
T squared_distance(const point<T> &p, const point<T> &q){
	return (p - q).squared_norm();
}
template<class T>
T doubled_signed_area(const point<T> &p, const point<T> &q, const point<T> &r){
	return q - p ^ r - p;
}
template<class T>
T doubled_signed_area(const vector<point<T>> &a){
	if(a.empty()) return 0;
	T res = a.back() ^ a.front();
	for(auto i = 1; i < (int)a.size(); ++ i) res += a[i - 1] ^ a[i];
	return res;
}
// [-pi, pi]
template<class T>
double angle(const point<T> &p, const point<T> &q){
	return atan2(p ^ q, p * q);
}
// [-pi, pi]
template<class T>
long double angle_l(const point<T> &p, const point<T> &q){
	return atan2l(p ^ q, p * q);
}
// Check if p->q->r is sorted by angle with respect to the origin
template<class T>
bool is_sorted_by_angle(const point<T> &origin, const point<T> &p, const point<T> &q, const point<T> &r){
	T x = p - origin ^ q - origin;
	T y = q - origin ^ r - origin;
	if(x >= 0 && y >= 0) return true;
	if(x < 0 && y < 0) return false;
	return (p - origin ^ r - origin) < 0;
}
template<class T>
struct compare_by_angle{
	point<T> origin;
	compare_by_angle(const point<T> &origin = point<T>()): origin(origin){ }
	int side(const point<T> &p) const{
		return p < origin ? -1 : p == origin ? 0 : 1;
	}
	bool operator()(const point<T> &p, const point<T> &q) const{
		int sp = side(p), sq = side(q);
		if(sp != sq) return sp < sq;
		return doubled_signed_area(origin, p, q) > 0;
	}
};
// Check if a is sorted by angle with respect to the origin
template<class T>
bool is_sorted_by_angle(const point<T> &origin, const vector<point<T>> &a){
	for(auto i = 0; i < (int)a.size() - 2; ++ i) if(!is_sorted_by_angle(origin, a[i], a[i + 1], a[i + 2])) return false;
	return true;
}
template<class T>
bool counterclockwise(const point<T> &p, const point<T> &q, const point<T> &r){
	return doubled_signed_area(p, q, r) > 0;
}
template<class T>
bool clockwise(const point<T> &p, const point<T> &q, const point<T> &r){
	return doubled_signed_area(p, q, r) < 0;
}
template<class T>
bool colinear(const point<T> &p, const point<T> &q, const point<T> &r){
	return doubled_signed_area(p, q, r) == 0;
}
template<class T>
bool colinear(const vector<point<T>> &a){
	int i = 1;
	while(i < (int)a.size() && a[0] == a[i]) ++ i;
	if(i == (int)a.size()) return true;
	for(auto j = i + 1; j < (int)a.size(); ++ j) if(!colinear(a[0], a[i], a[j])) return false;
	return true;
}
point<double> polar(double x, double theta){
	assert(x >= 0);
	return {x * cos(theta), x * sin(theta)};
}
point<long double> polar_l(long double x, long double theta){
	assert(x >= 0);
	return {x * cosl(theta), x * sinl(theta)};
}
// T must be able to hold the fourth power of max coordinate
// returns [a, b, c, and d lies in a circle]
template<class T>
bool concircular(point<T> a, point<T> b, point<T> c, const point<T> &d){
		a -= d, b -= d, c -= d;
	return a.squared_norm() * (b ^ c) + b.squared_norm() * (c ^ a) + c.squared_norm() * (a ^ b) == 0;
}
// T must be able to hold the fourth power of max coordinate
// returns [d lies in the interior of the circle defined by a, b, c]
template<class T>
bool inside_of_circle(point<T> a, point<T> b, point<T> c, const point<T> &d){
		a -= d, b -= d, c -= d;
	return (a.squared_norm() * (b ^ c) + b.squared_norm() * (c ^ a) + c.squared_norm() * (a ^ b)) * (doubled_signed_area(a, b, c) > 0 ? 1 : -1) > 0;
}
// T must be able to hold the fourth power of max coordinate
// returns [d lies in the exterior of the circle defined by a, b, c]
template<class T>
bool outside_of_circle(point<T> a, point<T> b, point<T> c, const point<T> &d){
		a -= d, b -= d, c -= d;
	return (a.squared_norm() * (b ^ c) + b.squared_norm() * (c ^ a) + c.squared_norm() * (a ^ b)) * (doubled_signed_area(a, b, c) > 0 ? -1 : 1) > 0;
}

using pointint = point<int>;
using pointll = point<long long>;
using pointlll = point<__int128_t>;
using pointd = point<double>;
using pointld = point<long double>;

// Requires point
template<class T>
struct convex_polygon{
	vector<point<T>> data;
	// Construct the convex polygon as the convex hull of a
	// O(n * log(n)) if is_sorted = false, O(n) otherwise
	convex_polygon(vector<point<T>> a = {}, bool is_sorted = false){
		if(!is_sorted) sort(a.begin(), a.end()), a.erase(unique(a.begin(), a.end()), a.end());;
		vector<point<T>> upper;
#define ADDP(C, cmp) while((int)C.size() > 1 && doubled_signed_area(C[(int)C.size() - 2], p, C.back()) cmp 0) C.pop_back(); C.push_back(p);
		for(auto &p: a){
			ADDP(data, >=)
			ADDP(upper, <=)
		}
#undef ADDP
		if((int)upper.size() >= 3) data.insert(data.end(), ++ upper.rbegin(), -- upper.rend());
	}
	friend ostream &operator<<(ostream &out, const convex_polygon &c){
		out << "{";
		for(auto p: c.data) out << p << ", ";
		return out << (c.empty() ? "" : "\b\b") << "}";
	}
	int size() const{
		return (int)data.size();
	}
	bool empty() const{
		return data.empty();
	}
	point<T> &operator[](int i){
		return data[i];
	}
	const point<T> &operator[](int i) const{
		return data[i];
	}
	point<T> &front(){
		return data.front();
	}
	const point<T> &front() const{
		return data.front();
	}
	point<T> &back(){
		return data.back();
	}
	const point<T> &back() const{
		return data.back();
	}
	// Returns the sorted list of points
	// O(n)
	vector<point<T>> linearize() const{
		if(data.empty()) return {};
		auto res = data;
		int p = max_element(res.begin(), res.end()) - res.begin();
		reverse(res.begin() + p + 1, res.end());
		inplace_merge(res.begin(), res.begin() + p + 1, res.end());
		return res;
	}
	// Merge two convex polygons
	// O(n + m)
	convex_polygon operator^(const convex_polygon &c) const{
		vector<point<T>> A = linearize(), B = c.linearize(), C((int)A.size() + (int)B.size());
		merge(A.begin(), A.end(), B.begin(), B.end(), C.begin());
		return {C, true};
	}
	convex_polygon &operator^=(const convex_polygon &c){
		return *this = *this ^ c;
	}
	convex_polygon &operator+=(const point<T> &p){
		for(auto &q: data) q += p;
		return *this;
	}
	convex_polygon operator+(const point<T> &p) const{
		return convex_polygon(*this) += p;
	}
	friend convex_polygon operator+(const point<T> &p, const convex_polygon &c){
		return c + p;
	}
	// O(n)
	vector<point<T>> boundary() const{
		assert((int)size() >= 2);
		auto res = data;
		res.push_back(res[0]);
		for(auto i = (int)res.size() - 1; i > 0; -- i) res[i] -= res[i - 1];
		return res;
	}
	// Minkowski addition
	// O(n + m)
	convex_polygon operator+(const convex_polygon &c) const{
		if(empty() || c.empty()) return {};
		if((int)size() == 1) return c + data[0];
		if((int)c.size() == 1) return *this + c[0];
		auto A = boundary(), B = c.boundary();
		convex_polygon res;
		res.data.resize(A.size() + B.size() - 1);
		res[0] = A[0] + B[0];
		merge(A.begin() + 1, A.end(), B.begin() + 1, B.end(), res.data.begin() + 1, [&](auto p, auto q){
			bool sign_p = p.x < 0 || p.x == 0 && p.y < 0;
			bool sign_q = q.x < 0 || q.x == 0 && q.y < 0;
			if(sign_p != sign_q) return sign_p < sign_q;
			else return (p ^ q) > 0;
		});
		for(auto i = 1; i < (int)res.size(); ++ i) res[i] += res[i - 1];
		assert(res.front() == res.back());
		int size = 1;
		for(auto i = 1; i < (int)res.size() - 1; ){
			while(i < (int)res.size() - 1 && colinear(res[i - 1], res[i], res[i + 1]) && (res[i] - res[i - 1]) * (res[i + 1] - res[i]) > 0) ++ i;
			if(i < (int)res.size() - 1) res[size ++] = res[i ++];
		}
		res.data.resize(size);
		return res;
	}
	convex_polygon &operator+=(const convex_polygon &c){
		return *this = *this + c;
	}
	// O(n)
	convex_polygon operator-() const{
		convex_polygon res = *this;
		for(auto &p: res.data) p = -p;
		rotate(res.data.begin(), min_element(res.data.begin(), res.data.end()), res.data.end());
		return res;
	}
	// O(n)
	convex_polygon operator-(const convex_polygon &c) const{
		return *this + -c;
	}
	convex_polygon &operator-=(const convex_polygon &c) const{
		return *this = *this + -c;
	}
};

int main(){
	cin.tie(0)->sync_with_stdio(0);
	cin.exceptions(ios::badbit | ios::failbit);
	cout << fixed << setprecision(15);
	int n;
	cin >> n;
	vector<pointll> a(n), b(n);
	copy_n(istream_iterator<pointll>(cin), n, a.begin());
	copy_n(istream_iterator<pointll>(cin), n, b.begin());
	convex_polygon cpa(a), cpb(b);
	double la = 0, lb = 0;
	for(auto i = 0; i < (int)cpa.size(); ++ i){
		la += distance(cpa[i], cpa[(i + 1) % (int)cpa.size()]);
	}
	for(auto i = 0; i < (int)cpb.size(); ++ i){
		lb += distance(cpb[i], cpb[(i + 1) % (int)cpb.size()]);
	}
	cout << lb / la << "\n";
	return 0;
}

/*

*/
yukicoder

結果

ソースコード
