QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#370083#2839. 3D GeometryPetroTarnavskyiAC ✓796ms3984kbC++205.2kb2024-03-28 21:45:372024-03-28 21:45:38

Judging History

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

  • [2024-03-28 21:45:38]
  • 评测
  • 测评结果:AC
  • 用时:796ms
  • 内存:3984kb
  • [2024-03-28 21:45:37]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, a, b) for(int i = (a) - 1; i >= (b); i--)
#define SZ(a) int(a.size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second

typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef long double db;

const db EPS = 1e-9;

struct Pt
{
	db x, y;
	Pt operator+(const Pt& p) const
	{
		return {x + p.x, y + p.y};
	}
	Pt operator-(const Pt& p) const
	{
		return {x - p.x, y - p.y};
	}
	Pt operator*(db d) const
	{
		return {x * d, y * d};
	}

	Pt operator/(db d) const
	{
		return {x / d, y / d};
	}
};

db sq(const Pt& p)
{
	return p.x * p.x + p.y * p.y;
}
db abs(const Pt& p)
{
	return sqrt(sq(p));
}
int sgn(db x)
{
	return (EPS < x) - (x < -EPS);
}
Pt perp(const Pt& p)
{
	return {-p.y, p.x};
}
db dot(const Pt& p, const Pt& q)
{
	return p.x * q.x + p.y * q.y;
}
db cross(const Pt& p, const Pt& q)
{
	return p.x * q.y - p.y * q.x;
}
bool half(const Pt& p)
{
	assert(sgn(p.x) != 0 || sgn(p.y) != 0);
	return sgn(p.y) == -1 ||
		(sgn(p.y) == 0 && sgn(p.x) == -1);
}

struct Line
{
	Pt n;
	db c;
	Line(const Pt& p, const Pt& q):
		n(perp(q - p)), c(-dot(n, p)) {}
	
	db side(const Pt& p) const
	{
		return dot(n, p) + c;
	}

};

bool parallel(const Line& l1, const Line& l2)
{
	return sgn(cross(l1.n, l2.n)) == 0;
}
Pt inter(const Line& l1, const Line& l2)
{
	db d = cross(l1.n, l2.n);
	assert(sgn(d) != 0);
	return perp(l2.n * l1.c - l1.n * l2.c) / d;
}
db areaPolygon(const vector<Pt>& v)
{
	db area = 0.0;
	int n = SZ(v);
	FOR(i, 0, n)
		area += cross(v[i], v[(i + 1) % n]);
	return abs(area) / 2.0;
}

vector<Pt> hplaneInter(vector<Line> lines)
{
	sort(ALL(lines), [](const Line& l1, const Line& l2)
	{
		bool h1 = half(l1.n), h2 = half(l2.n);
		if (h1 != h2)
			return h1 < h2;
		int p = sgn(cross(l1.n, l2.n));
		if (p != 0)
			return p > 0;
		return sgn(l1.c / abs(l1.n) - l2.c / abs(l2.n)) < 0;
	});
	lines.erase(unique(ALL(lines), parallel), lines.end());
	deque<pair<Line, Pt>> d;
	for (const Line& l : lines)
	{
		while (SZ(d) > 1 && sgn(l.side((d.end() - 1)->S)) < 0)
			d.pop_back();
		while (SZ(d) > 1 && sgn(l.side((d.begin() + 1)->S)) < 0)
			d.pop_front();
		if (!d.empty() && sgn(cross(d.back().F.n, l.n)) <= 0)
			return {};
		if (SZ(d) < 2 || sgn(d.front().F.side(inter(l, d.back().F))) >= 0)
		{
			Pt p;
			if (!d.empty())
			{
				p = inter(l, d.back().F);
				if (!parallel(l, d.front().F))
					d.front().S = inter(l, d.front().F);
			}
			d.PB({l, p});
		}
	}
	vector<Pt> res;
	for (auto [l, p] : d)
	{
		if (res.empty() || sgn(sq(p - res.back())) > 0)
			res.PB(p);
	}
	return res;
}

db x[4], y[4], z[4];

tuple<db, db, db> cross(db x1, db y1, db z1, db x2, db y2, db z2)
{
	return {y1 * z2 - z1 * y2, z1 * x2 - x1 * z2, x1 * y2 - y1 * x2};
}

void solve()
{
	FOR(i, 1, 4)
		cin >> x[i] >> y[i] >> z[i];
	vector<db> zs = {(db)z[0], (db)z[1], (db)z[2], (db)z[3]};
	auto [a, b, c] = cross(x[0] - x[1], y[1] - y[0], 0, x[0] - x[1], 0, z[1] - z[0]);
	db d = -a * x[1] - b * y[0] - c * z[0];
	
	//cerr << "d = " << d << endl;
	if (x[2] > x[3])
		swap(x[2], x[3]);
	if (y[2] > y[3])
		swap(y[2], y[3]);
	if (z[2] > z[3])
		swap(z[2], z[3]);
	FOR(i, 0, 4)
	{
		FOR(j, 0, 4)
		{
			zs.PB(((db)-a * x[i] - b * y[j] - d) / c);
		//	cerr << zs.back() << "\n";
		}
	}
	sort(ALL(zs));
	vector<Line> lines;
	lines.PB({{x[2], y[2]}, {x[3], y[2]}});
	lines.PB({{x[3], y[2]}, {x[3], y[3]}});
	lines.PB({{x[3], y[3]}, {x[2], y[3]}});
	lines.PB({{x[2], y[3]}, {x[2], y[2]}});
	Pt p = {x[0], y[0]}, q = {x[1], y[0]}, r = {x[0], y[1]};
	FOR(it, 0, 2)
	{
		if (sgn(cross(q - p, r - p)) > 0)
			lines.PB({p, q});
		else
			lines.PB({q, p});
		swap(q, r);
	}
	auto f = [&](db zet)
	{
		db alpha = (zet - z[1]) / (z[0] - z[1]);
		if (sgn(alpha) == 0)
		{
			return db(0.0);
		}
		Pt qAlpha = p + (q - p) * alpha;
		Pt rAlpha = p + (r - p) * alpha;
		if (sgn(cross(q - p, r - p)) > 0)
			lines.PB({qAlpha, rAlpha});
		else
			lines.PB({rAlpha, qAlpha});
		db res = areaPolygon(hplaneInter(lines));
		lines.pop_back();
		return res;
	};
	/*for (auto zet : zs)
		cerr << zet << " ";
	cerr << endl;*/
	db ans = 0;
	FOR(i, 0, SZ(zs) - 1)
	{
		db z1 = zs[i], z2 = (zs[i] + zs[i + 1]) / 2.0, z3 = zs[i + 1];
		if ((z2 < min(z[0], z[1]) || z2 > max(z[0], z[1]) || z2 < min(z[2], z[3]) || z2 > max(z[2], z[3])))
			continue;
		//cerr << i << '\n';
		//cerr << z1 << " " << z2 << " " << z3 << endl;
		//cerr << "z1  " << z1 << " " << f(z1) << endl;
		//cerr << "z2  " << z2 << " " << f(z2) << endl;
		//cerr << "z3  " << z3 << " " << f(z3) << endl;
		ans += (z3 - z1) * (f(z1) + 4 * f(z2) + f(z3));
	}
	//if (abs(ans - 7.500000) < 1e-3)
	//{
	//	cout << setprecision(1);
	//	FOR (i, 0, 4)
	//	{
	//		cout << x[i] << '#' << y[i] << '#' << z[i] << '$';
	//	}
	//	return;
	//}
	cout << ans / 6 << "\n";
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout << fixed << setprecision(15);
	while (cin >> x[0] >> y[0] >> z[0])
		solve();
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

0 0 0
1 1 1
0 0 0
1 1 1
0 0 0
2 2 2
0 0 0
1 1 1
0 2 0
2 0 2
1 0 1
0 1 0

output:

0.166666666666667
0.833333333333333
0.166666666666667

result:

ok 3 numbers

Test #2:

score: 0
Accepted
time: 796ms
memory: 3848kb

input:

-3 -4 2
-5 -5 4
0 0 3
3 4 2
1 5 2
-4 0 0
5 -5 0
-2 -1 3
5 4 2
3 -5 -1
0 -2 -1
-4 -4 -3
-4 4 -2
-2 2 -1
2 2 1
4 0 5
-4 1 0
-5 -2 4
-5 2 -4
5 0 1
2 5 1
-1 0 -3
-1 5 -4
-4 2 -2
2 2 -4
1 3 -1
2 4 2
-2 1 3
2 5 2
-2 -3 -5
-1 0 0
5 4 2
2 5 3
-3 -3 -3
5 4 -4
1 2 -3
2 -4 2
-3 -2 -2
2 -2 -1
-4 -5 3
4 -3 -3
-3...

output:

0.000000000000000
0.000000000000000
0.000000000000000
0.000000000000000
0.708333333333333
0.000000000000000
0.000000000000000
15.355654761904762
0.000000000000000
6.562500000000000
0.000000000000000
0.000000000000000
0.000000000000000
0.000000000000000
0.000000000000000
0.000000000000000
0.000000000...

result:

ok 100000 numbers

Test #3:

score: 0
Accepted
time: 720ms
memory: 3952kb

input:

-2 -2 -9
1 7 6
-3 -1 -4
-5 -6 2
-3 -4 -9
-10 -5 -4
0 2 -6
7 -9 2
6 4 5
-2 -6 0
8 -8 -3
-3 -10 2
10 -3 -8
-7 -5 -10
-9 -5 1
10 8 -1
7 9 10
6 3 9
-10 -10 -4
0 2 1
-2 4 9
10 5 -4
-6 6 3
7 4 8
6 5 2
3 -7 8
2 3 1
4 -10 7
-7 -3 -6
-10 5 -9
0 3 1
-5 -6 8
5 -3 8
-8 -8 -4
5 -10 4
0 3 1
9 -9 0
-8 8 -3
-7 9 -2...

output:

0.000000000000000
0.000000000000000
0.000000000000000
0.000000000000000
0.000000000000000
16.255732248520710
0.166666666666667
0.000000000000000
26.201923076923077
1.449891067538126
0.000000000000000
0.000000000000000
0.000000000000000
0.000000000000000
1.280276816608997
0.000000000000000
0.00000000...

result:

ok 100000 numbers

Test #4:

score: 0
Accepted
time: 689ms
memory: 3952kb

input:

91 49 27
-66 89 -21
-22 35 78
-64 41 -19
93 87 -92
72 -32 -67
-48 28 -6
-50 20 78
-33 90 41
75 -51 43
89 9 -89
-35 -73 88
13 13 82
82 -40 72
-21 -75 36
15 79 -66
-21 -99 -49
-33 60 78
-27 -86 -64
61 66 96
-77 37 -71
72 -35 -9
38 86 -68
51 65 15
-16 -64 -25
-72 23 81
-20 60 60
-52 -99 19
24 83 27
-11...

output:

0.000000000000000
0.000000000000000
391.127206880941601
0.000000000000000
28313.212264150943398
0.000000000000000
11477.662564206886030
4368.006677005977706
14406.483590595559708
5814.427201070791197
0.000000000000000
50112.716889796352838
0.000000000000000
0.000000000000000
0.000000000000000
0.0000...

result:

ok 100000 numbers

Test #5:

score: 0
Accepted
time: 674ms
memory: 3928kb

input:

-67 241 62
-271 -19 -199
364 487 343
293 433 -343
346 -321 78
-119 68 -487
-319 -45 -165
465 142 491
-310 476 -388
419 409 -124
167 -448 362
233 341 -119
9 -422 290
202 321 -217
310 216 286
172 10 -220
77 107 -282
352 -438 -26
171 81 111
-192 70 -132
376 -361 246
-371 354 -77
-400 -224 457
118 -387 ...

output:

0.000000000000000
417528.646965721876086
0.000000000000000
0.000000000000000
49064.274495412844026
5211742.513100331297665
3370766.246515173515490
0.000000000000000
0.000000000000000
84.405133541449877
165311.117708426522356
0.000000000000000
0.000000000000000
0.000000000000000
52736.152560963166984...

result:

ok 100000 numbers