QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#344527#7783. Military Maneuverucup-team1209WA 43ms3992kbC++202.7kb2024-03-04 18:35:522024-03-04 18:35:52

Judging History

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

  • [2024-03-04 18:35:52]
  • 评测
  • 测评结果:WA
  • 用时:43ms
  • 内存:3992kb
  • [2024-03-04 18:35:52]
  • 提交

answer

#include<bits/stdc++.h>
using std::cin, std::cout;
using ll = long long;
using u64 = unsigned long long;
using db = double;
using f64 = long double;
struct vec2 {
	db x, y;
	db norm() const { return x * x + y * y; }
	db abs() const { return std::sqrt(norm()); }
};
const db eps = 1e-8;
db sgn(db x) {
	return x < -eps ? -1 : x > eps;
}
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}; }
f64 operator * (vec2 x, vec2 y) { return x.x * y.y - x.y * y.x; }
vec2 r90(vec2 x) {
	return {-x.y, x.x};
}
struct line : vec2 {
	db z;
	line(db a, db b, db c) : vec2({a, b}), z(c) {}
	line(vec2 a, vec2 b) : vec2(r90(b - a)), z(a * b) {}
	db operator () (vec2 o) const { return o.x * x + o.y * y + z; }
	line perp() const { return {y, -x, 0}; }
	line para(vec2 o) { return {x, y, z - (*this)(o) }; }
	db abs() const { return sqrt(x * x + y * y); }
	db side(vec2 x) const {
		return sgn((*this)(x) / abs());
	}
};
vec2 operator & (line x, line y) {
	return vec2{vec2{x.z, x.y} * vec2{y.z, y.y}, vec2{x.x, x.z} * vec2{y.x, y.z}} / -(vec2(x) * vec2(y));
}
line bisector(vec2 a, vec2 b) {
	return line(b, a).perp().para((a + b) / 2);
}
f64 det(line a, line b, line c) {
	vec2 A = a, B = b, C = c;
	return c.z * (A * B) + a.z * (B * C) + b.z * (C * A);
}
db check(line a, line b, line c) {
	return sgn(det(a, b, c)) * sgn(vec2(a) * vec2(b));
}
std::vector<vec2> cut(const std::vector<vec2> & o, line l) {
	std::vector<vec2> res;
	int n = size(o);
	for(int i = 0;i < n;++i) {
		vec2 a = o[i], b = o[(i + 1) % n];
		if(l.side(a) >= 0) res.push_back(a);
		if(l.side(a) * l.side(b) < 0) res.push_back(line(a, b) & l);
	}
	return res;
}
db calc(std::vector<vec2> v, vec2 p) {
	db sum = 0;
	for(int i = 0;i < (int) v.size();++i) {
		vec2 a = v[i] - p, b = v[(i + 1) % v.size()] - p;
		sum += a * b * (a.norm() / 3 + b.norm() / 3 + (a * b) / 6);
	}
	return sum;
}
db calc(std::vector<vec2> p, std::vector<vec2> init) {
	std::mt19937 gen(114514);
	shuffle(p.begin(), p.end(), gen);
	db ans = 0;
	for(int i = 0;i < (int) p.size();++i) {
		auto A = init, B = init;
		for(vec2 x : p) if((x - p[i]).abs() > eps) {
			A = cut(A, bisector(p[i], x));
			B = cut(B, bisector(x, p[i]));
		}
		ans += calc(B, p[i]);
		ans -= calc(A, p[i]);
	}
	return ans;
}

db xl, yl, xr, yr;
int main() {
	cin >> xl >> yl >> xr >> yr;
	int n; cin >> n;
	std::vector<vec2> a(n);
	for(auto & [x, y] : a) cin >> x >> y;
	db res = calc(a, { {xl, yl}, {xr, yl}, {xr, yr}, {xl, yr} });
	printf("%.10lf\n", res / (xr - xl) / (yr - yl) * std::acos(-1) / 3);
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3992kb

input:

0 0 2 2
2
3 1
1 3

output:

8.3775804096

result:

ok found '8.3775804', expected '8.3775804', error '0.0000000'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3776kb

input:

0 0 2 2
2
5 1
1 3

output:

37.6991118431

result:

ok found '37.6991118', expected '37.6991118', error '0.0000000'

Test #3:

score: -100
Wrong Answer
time: 43ms
memory: 3904kb

input:

-2911 2151 336 5941
2000
-83 79
-94 47
48 -29
-47 64
84 75
-44 -86
-58 -11
-31 58
20 53
80 -19
-82 74
-60 -26
8 -68
-42 -61
-14 12
-58 -18
92 10
35 -26
71 64
76 89
-80 6
70 4
-96 -99
95 -80
-3 -22
71 -89
-75 17
-35 -82
-59 95
60 48
-74 50
-82 90
-26 5
-75 -31
-45 85
85 14
-70 -57
59 46
55 13
-23 60
...

output:

6794254.7831411967

result:

wrong answer 1st numbers differ - expected: '6657168.1428534', found: '6794254.7831412', error = '0.0205923'