QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#332751#7734. Intersection over Unionucup-team1209WA 453ms3936kbC++202.5kb2024-02-19 15:56:282024-02-19 15:56:29

Judging History

你现在查看的是最新测评结果

  • [2024-02-19 15:56:29]
  • 评测
  • 测评结果:WA
  • 用时:453ms
  • 内存:3936kb
  • [2024-02-19 15:56:28]
  • 提交

answer

#include<bits/stdc++.h>
using ll = long long;
const int N = 1005;
using std::cin, std::cout;
using db = long double;
struct vec2 {
	db x, y;
	db norm() const {
		return x * x + y * y;
	}
};
vec2 operator + (vec2 x, vec2 y) { return {x.x + y.x, x.y + y.y}; }
vec2 operator - (vec2 x, vec2 y) { return {x.x - y.x, x.y - y.y}; }
vec2 operator * (vec2 x, db y) { return {x.x * y, x.y * y}; }
vec2 r90(vec2 x) { return {-x.y, x.x}; }
db operator * (vec2 x, vec2 y) { return x.x * y.y - x.y * y.x; }
db operator % (vec2 x, vec2 y) { return x.x * y.x + x.y * y.y; }
vec2 get() {
	int x, y; cin >> x >> y;
	return {(db)x,db(y)};
}
const db eps = 1e-12;
struct func {
	vec2 o;
	db c;
	db prod;
	bool init(vec2 a, vec2 b) {
		o = r90(a - b);
		if(o.x < 0) a.x *= -1, b.x *= -1, std::swap(a, b);
		if(o.y < 0) a.y *= -1, b.y *= -1, std::swap(a, b);
		o = r90(a - b);
		if(fabs(o.x) < eps) return 0;
		if(fabs(o.y) < eps) return 0;
		o = o * (1 / sqrt(o.norm()));
		c = o % a;
		prod = o.norm() / o.x / o.y;
		return 1;
	}
	db calc(db x, db y) const {
		db v = std::max<db>(0, x * o.x + y * o. y - c);
		return v * v * prod;
	}
} pb, fsy;
db f(db x, db y) {
	return pb.calc(x, y) + fsy.calc(x, y);
}
db S;
db g(db x, db y) {
	db r = f(x, y);
	return (4 * x * y - r) / (S + r);
}
db ly, ry;
db best(db x) {
	db l = 0, r = ry;
	for(int i = 0;i < 45;++i) {
		db ml = l * 0.55 + r * 0.45;
		db mr = l * 0.45 + r * 0.55;
		if(g(x, ml) > g(x, mr)) {
			r = mr;
		} else {
			l = ml;
		}
	}
	return g(x, (l + r) / 2);
}
db findmax(db a, db c, auto f) {
	auto g = [&](db l, db r) {
		return l + (r - l) * (std::numbers::phi_v<db> - 1);
	};
	db b = g(a, c), bv = f(b);
	for(int i = 0;i < 40;++i) {
		db x = g(a, b), xv = f(x);
		if(xv > bv) {
			c = b, b = x, bv = xv;
		} else {
			a = c, c = x;
		}
	}
	return bv;
}
int main() {
	std::ios::sync_with_stdio(false), cin.tie(0);
	int T; cin >> T;
	for(int i = 0;i < T;++i) {
		vec2 a[4];
		vec2 s = {};
		for(auto & x : a) x = get(), s = s + x;
		if((a[1] - a[0]) * (a[2] - a[0]) < 0) {
			std::reverse(a, a + 4);
		}
		s = s * 0.25;
		for(auto & x : a) x = x - s, x = x * (1 / sqrt(x.norm()));
		S = (a[1] - a[0]) * (a[2] - a[0]);
		if(!pb.init(a[0], a[1])) {
			puts("1");
			continue;
		}
		if(!fsy.init(a[1], a[2])) {
			puts("1");
			continue;
		}
		db l = 0, r = a[0].x;
		ry = a[0].y;
		for(auto & x : a) {
			r = std::max(r, x.x);
			ry = std::max(ry, x.y);
		}
		printf("%.12Lf\n", findmax(l, r, best));
	}

}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3936kb

input:

3
0 2 2 0 0 -2 -2 0
7 -2 9 -2 9 2 7 2
7 13 11 10 5 2 1 5

output:

0.707106781187
1
0.623843224831

result:

ok 3 numbers

Test #2:

score: -100
Wrong Answer
time: 453ms
memory: 3876kb

input:

10000
-568767734 379152673 -565681345 -54946093 -131582579 -51859704 -134668968 382239062
-194884120 -559906233 -194884142 -158042604 -998611400 -158042648 -998611378 -559906277
459335966 -945199065 478030260 -934243779 450535683 -887326546 431841389 -898281832
-483567491 491964356 -523827401 408140...

output:

0.992965412526
0.999999931569
0.590869815679
0.621770484911
0.578832384135
1
0.499999997374
0.685234580574
0.455961719767
0.500287393902
0.980296110592
0.492043571792
0.544037388707
0.380480107105
0.923118331764
0.892558700860
0.617680319575
0.945676970215
0.499874372003
0.999954387824
0.64742147647...

result:

wrong answer 171st numbers differ - expected: '0.9490512', found: '0.9490512', error = '0.0000000'