QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#369958#2827. AutobiographyPetroTarnavskyi#WA 0ms3720kbC++204.6kb2024-03-28 20:06:562024-03-28 20:06:56

Judging History

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

  • [2024-03-28 20:06:56]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3720kb
  • [2024-03-28 20:06:56]
  • 提交

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 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, 2, 4)
	{
		FOR(j, 2, 4)
		{
			zs.PB((db)(-a * x[i] - b * y[j] - d) / c);
		}
	}
	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 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;
	};
	const int MAGIC = 1e4;
	db zMin = max(min(z[0], z[1]), z[2]), zMax = min(max(z[0], z[1]), z[3]);
	db ans = 0;
	FOR(i, 0, MAGIC)
	{
		db zet = zMin + (i + 0.5) / MAGIC * (zMax - zMin);
		ans += f(zet);
	}
	cout << ans * (zMax - zMin) / MAGIC << "\n";
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout << fixed << setprecision(4);
	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: 0
Wrong Answer
time: 0ms
memory: 3720kb

input:

5 4
bbobo
1 3
2 3
3 4
4 5
4 6
bobo
1 2
1 3
1 4
2 3
2 4
3 4
4 0
bobo

output:


result:

wrong answer 1st lines differ - expected: '2', found: ''