QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#797964 | #5809. Min Perimeter | BananaMac | 20 ✓ | 9860ms | 66452kb | C++20 | 14.2kb | 2024-12-03 21:58:21 | 2024-12-03 21:58:21 |
Judging History
answer
/**
* 15:15:28 9/27/24
* Point
*/
// ./ICPC/Geometry/OrganizedTemplates/Point.cpp
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define int long long
#define uint unsigned int
#define double long double
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);
#define nl '\n'
#define all(v) v.begin(), v.end()
#define NO (cout << "NO" << nl);
#define YES (cout << "YES" << nl);
#define F first
#define S second
#define INF LONG_LONG_MAX
#define pii pair<int, int>
#define vec vector
#define LT int T; cin >> T; while (T--)
template<typename T>
using vec2d = vector<vector<T>>;
template<typename T>
using ordered_set = tree<T, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update>;
using indexed_set = tree<int, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update>;
namespace Geometry {
using ftype = double;
using atype = double;
const double eps = 1e-9l;
const double pi = acos(-1.0l);
// const double e = exp(1.0L);
const double inf = 1e18l;
const int mod = 1e9 + 7;
const int iinf = LONG_LONG_MAX;
int32_t prec = 25;
bool useDoubleIn = false;
ftype sqr(ftype v) { return v * v; }
void setPrec(ostream& out = cout) {
out << fixed << setprecision(prec);
}
//bool eq(const ftype& a, const ftype& b) {
// return a == b;
//}
bool eq(const ftype& a, const ftype& b) {
return abs(a - b) < eps;
}
//bool ls(const ftype& a, const ftype& b) {
// return a < b;
//}
bool ls(const ftype& a, const ftype& b) {
return (b - a) > eps;
}
//bool lse(const ftype& a, const ftype& b) {
// return a <= b;
//}
bool lse(const ftype& a, const ftype& b) {
return ls(a, b) or eq(a, b);
}
//bool bt(const ftype& a, const ftype& b, const ftype& c) {
// return a < b and b < c;
//}
bool bt(const ftype& a, const ftype& b, const ftype& c) {
return ls(a, b) and ls(b, c);
}
//bool bte(const ftype& a, const ftype& b, const ftype& c) {
// return a <= b and b <= c;
//}
bool bte(const ftype& a, const ftype& b, const ftype& c) {
return lse(a, b) and lse(b, c);
}
ftype max(const ftype& a, const ftype& b) {
return ls(a, b) ? b : a;
}
int max(int a, int b) {
return a < b ? b : a;
}
ftype min(const ftype& a, const ftype& b) {
return ls(a, b) ? a : b;
}
int min(int a, int b) {
return a < b ? a : b;
}
optional<array<ftype, 2>> quadratic(ftype a, ftype b, ftype c) {
ftype discriminant = b * b - 4 * a * c;
if (ls(discriminant, 0)) {
return nullopt;
}
ftype sqrtD = sqrt(discriminant);
return array<ftype, 2>{(-b + sqrtD) / (2 * a), (-b - sqrtD) / (2 * a)};
}
// Returns angle with respect to the x-axis.
atype angle(atype x, atype y) {
return atan2(y, x);
}
atype torad(atype a) { return a / 180 * pi; }
atype todeg(atype a) { return a / pi * 180; }
int sign(const ftype& v) {
if (ls(0, v)) return 1;
else if (ls(v, 0)) return -1;
return 0;
}
pair<int, int> reduce(ftype v0, ftype v1) {
// log(n)
int a = (int)v0, b = (int)v1;
if (a == 0) return {0, sign(b)};
if (b == 0) return {sign(a) * iinf, 0};
int g = gcd(a, b);
return {a / g, b / g};
}
pair<int, int> reducef(ftype v0, ftype v1) {
// log(n)
return reduce(v0 * 1e6l, v1 * 1e6l);
}
// 2D point
struct P {
ftype x, y;
static P polar(const ftype& r, const atype& a) {
return {r * cos(a), r * sin(a)};
}
P(): x{0}, y{0} {}
P(ftype x, ftype y): x{x}, y{y} {}
explicit P(const complex<ftype>& p): P(p.real(), p.imag()) {}
explicit P(const pair<ftype, ftype>& p): P(p.F, p.S) {}
P(const P& p): P(p.x, p.y) {}
explicit operator complex<ftype>() const {
return {x, y};
}
explicit operator pair<ftype, ftype>() const {
return {x, y};
}
ftype dist(const P& p) const {
return (*this - p).abs();
}
ftype dist2(const P& p) const {
return (*this - p).norm();
}
atype r() const {
return hypot(x, y);
}
atype a() const {
return Geometry::angle(x, y);
}
atype ua(const P& p) const {
// undirected angle
double v0 = fabs(a() - p.a()), v1 = fabs(p.ap() - ap());
if (ls(v0, v1)) return v0;
else return v1;
}
atype ap() const {
atype res = Geometry::angle(x, y);
if (res < 0) res += 2 * pi;
return res;
}
atype angle(const P& p) const {
return acos(dot(p) / (abs() * p.abs()));
}
P operator-() const {
return *this * -1;
}
P operator+() const {
return *this;
}
P operator+=(const P& p) {
x += p.x;
y += p.y;
return *this;
}
P operator-=(const P& p) {
x -= p.x;
y -= p.y;
return *this;
}
P operator*=(const ftype& v) {
x *= v;
y *= v;
return *this;
}
P operator/=(const ftype& v) {
x /= v;
y /= v;
return *this;
}
P operator%=(const ftype& v) {
x = fmod(x, v);
y = fmod(y, v);
return *this;
}
P operator^=(const ftype& an) {
return *this = rotateccw(an);
}
P operator|=(const ftype& an) {
return *this = rotatecw(an);
}
P operator|(const ftype& an) {
P res = *this;
res |= an;
return res;
}
P operator^(const ftype& an) {
P res = *this;
res ^= an;
return res;
}
P operator+(const P& p) const {
P res = *this;
res += p;
return res;
}
P operator-(const P& p) const {
P res = *this;
res -= p;
return res;
}
P operator*(const ftype& v) const {
P res = *this;
res *= v;
return res;
}
P operator/(const ftype& v) const {
P res = *this;
res /= v;
return res;
}
P operator%(const ftype& v) const {
P res = *this;
res %= v;
return res;
}
bool operator==(const P& p) const {
return eq(x, p.x) and eq(y, p.y);
}
bool operator<(const P& p) const {
return eq(p.x, x) ? ls(y, p.y) : ls(x, p.x);
}
bool ycmp(const P& p) const {
return eq(p.y, y) ? ls(x, p.x) : ls(y, p.y);
}
bool operator<=(const P& p) const {
return *this < p or *this == p;
}
ftype slope() const {
return y / x;
}
pair<int, int> fslope() const {
return reduce(y, x);
}
pair<int, int> inorm() const {
return reduce(x, y);
}
ftype cross(const P& b, const P& c) const {
return (b - *this).cross(c - *this);
}
bool is_point_in_angle(P b, const P& a, P c) const {
// does point p lie in angle <bac
assert(c.orientation(a, b) != 0);
if (a.orientation(c, b) < 0) swap(b, c);
return a.orientation(c, *this) >= 0 && a.orientation(b, *this) <= 0;
}
// 1 this is to right of ab, 0 collinear, -1 to left
int orientation(const P& a, const P& b) const {
// orientation of this with respect to AB
const P& c = *this;
ftype d = (b - c).cross(a - c);
return sign(d);
}
ftype cross(const P& p) const {
return x * p.y - y * p.x;
}
ftype dot(const P& p) const {
return x * p.x + y * p.y;
}
ftype dot(const P& a, const P& b) const {
return (a - *this).dot(b - *this);
}
ftype norm() const {
return dot(*this);
}
atype abs() const {
return sqrt((atype)norm());
}
P truncate(ftype v) const {
// returns a vector with norm v and having same direction
ftype k = abs();
if (sign(k) == 0) return *this;
v /= k;
return *this * v;
}
P normalize() const {
return truncate(1);
}
P normal_l() const {
return {-y, x};
}
P normal_r() const {
return {y, -x};
}
P normal_lfs() const {
return P(fslope()).normal_l();
}
P normal_rfs() const {
return P(fslope()).normal_r();
}
P rotateccw(const atype& angle, const P& ref = {0, 0}) const {
P res;
ftype xs = x - ref.x, ys = y - ref.y;
res.x = ref.x + (xs * cos(angle) - ys * sin(angle));
res.y = ref.y + (xs * sin(angle) + ys * cos(angle));
return res;
}
P rotatecw(const atype& angle, const P& ref = {0, 0}) const {
return rotateccw(-angle, ref);
}
friend P operator*(const ftype& v, const P& p) {
return p * v;
}
friend istream& operator>>(istream& in, P& p) {
if (useDoubleIn) {
return in >> p.x >> p.y;
}
int xv, yv;
in >> xv >> yv;
p = P(xv, yv);
return in;
}
friend ostream& operator<<(ostream& out, const P& p) {
setPrec(out);
return out << "(" << p.x << ", " << p.y << ")";
}
};
// basic comparison functions
auto angleCmp = [](const P& p0, const P& p1) -> bool {
return ls(p0.a(), p1.a());
};
auto radiusCmp = [](const P& p0, const P& p1) -> bool {
return ls(p0.r(), p1.r());
};
auto stdCmp = [](const P& p0, const P& p1) -> bool {
return p0 < p1;
};
auto xCmp = [](const P& p0, const P& p1) -> bool {
return ls(p0.x, p1.x);
};
auto yCmp = [](const P& p0, const P& p1) -> bool {
return ls(p0.y, p1.y);
};
// Hash function
struct p_hash {
static __int128 splitmix128(__int128 x) {
// gr = 0x9e3779b97f4a7c15f39cc0605cedc835
// c0 = 0xbf58476d1ce4e5b9a3f7b72c1e3c9e3b
// c1 = 0x94d049bb133111ebb4093822299f31d7
__int128 gr = 0x9e3779b97f4a7c15, c0 = 0xbf58476d1ce4e5b9, c1 = 0x94d049bb133111eb;
gr <<= 64;
c0 <<= 64;
c1 <<= 64;
gr += 0xf39cc0605cedc835;
c0 += 0xa3f7b72c1e3c9e3b;
c1 += 0xb4093822299f31d7;
x += gr;
x = (x ^ (x >> 62)) * c0;
x = (x ^ (x >> 59)) * c1;
return x ^ (x >> 63);
}
size_t operator()(const P& p) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
__int128 x = (((__int128)p.x) << 64) | ((__int128)p.y);
return splitmix128(x + FIXED_RANDOM);
}
};
P inf_pt{inf, inf};
double heron(const P& p1, const P& p2, const P& p3) {
double a = p1.dist(p2);
double b = p1.dist(p3);
double c = p3.dist(p2);
double s = (a+b+c)/2.0;
double area = sqrt( s*(s-a)*(s-b)*(s-c) );
return area;
}
bool isCollinear(const P& a, const P& b, const P& c) {
return eq(0, heron(a, b, c));
}
}
using namespace Geometry;
ftype minper;
vec<P> btr;
int n;
vec<P> a, t;
bool cmp_x(const P& p0, const P& p1) {
return p0 < p1;
}
bool cmp_y(const P& p0, const P& p1) {
return ls(p0.y, p1.y);
}
void upd_ans_t(const P& p0, const P& p1, const P& p2) {
ftype per = p0.dist(p1) + p0.dist(p2) + p1.dist(p2);
if (ls(per, minper)) {
minper = per;
btr = {p0, p1, p2};
}
}
void rec_t(int l, int r) {
if (r - l <= 3) {
// Check all triangles in this small range
for (int i = l; i < r; ++i) {
for (int j = i + 1; j < r; ++j) {
for (int k = j + 1; k < r; ++k) {
upd_ans_t(a[i], a[j], a[k]);
}
}
}
sort(a.begin() + l, a.begin() + r, cmp_y);
return;
}
int m = (l + r) >> 1;
ftype midx = a[m].x;
rec_t(l, m);
rec_t(m, r);
merge(a.begin() + l, a.begin() + m, a.begin() + m, a.begin() + r, t.begin(), cmp_y);
copy(t.begin(), t.begin() + r - l, a.begin() + l);
vec<P> strip;
for (int i = l; i < r; ++i) {
if (ls(abs(a[i].x - midx), minper / 2)) {
for (int j = (int)strip.size() - 1; j >= 0 && ls(a[i].y - strip[j].y, minper / 2); --j) {
for (int k = j - 1; k >= 0 && ls(a[i].y - strip[k].y, minper / 2); --k) {
upd_ans_t(a[i], strip[j], strip[k]);
}
}
strip.push_back(a[i]);
}
}
}
void find_mn_t() {
t.resize(n);
sort(all(a), cmp_x);
minper = 1e20;
rec_t(0, n);
}
void solve() {
cin >> n;
a.resize(n);
for (P& p: a) cin >> p;
find_mn_t();
cout << setprecision(25) << fixed << minper << nl;
}
int32_t main() {
fast
const string NAME{" "};
if (NAME != " ") {
freopen((NAME + ".in").c_str(), "r", stdin);
freopen((NAME + ".out").c_str(), "w", stdout);
}
int T, tt;
cin >> T; tt = T;
while (T--) {
cout << "Case #" << tt - T << ": ";
solve();
}
}
詳細信息
Subtask #1:
score: 5
Accepted
Test #1:
score: 5
Accepted
time: 56ms
memory: 4180kb
input:
15 3 2 6 7 0 3 0 3 713 269 371 79 455 421 3 91983245 637281504 756917015 312173515 869576338 436726680 10000 14761642 78236002 9047458 47951098 5238002 27761162 476182 2523742 1428546 7571226 26190010 138805810 21904372 116092132 18094916 95902196 43332562 229660522 55237112 292754072 52380020 27761...
output:
Case #1: 17.8930122062048740823325677 Case #2: 1042.8448349643881045700766208 Case #3: 1711142102.7913271078141406178474426 Case #4: 90912.2963740329243265136938135 Case #5: 3.4142135623730950487637881 Case #6: 26.1538303421636949327305777 Case #7: 1701.0126810956169113309144336 Case #8: 2865438.191...
result:
ok correct! (15 test cases)
Subtask #2:
score: 15
Accepted
Test #2:
score: 15
Accepted
time: 9860ms
memory: 66452kb
input:
15 3 501691275 344354353 167768963 536043860 249445040 557426549 4 1000000000 0 0 0 1000000000 1000000000 0 1000000000 1000000 138925776 669369648 61257680 295150640 170762328 822763944 55483472 267329456 97736936 470914328 84041848 404928904 18463588 88960924 124429360 599523280 95066048 458045504 ...
output:
Case #1: 799653579.1330897417501546442508698 Case #2: 3414213562.3730950488243252038955688 Case #3: 866.0715905743589277943073057 Case #4: 62459.8953696371481782989576459 Case #5: 59141.9183589317811033936322929 Case #6: 898195.0909682679932757309870794 Case #7: 1707085.7699867850540158542571589 Cas...
result:
ok correct! (15 test cases)
Extra Test:
score: 0
Extra Test Passed