QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#308202#7783. Military ManeuvermshcherbaRE 0ms0kbC++204.7kb2024-01-19 18:30:442024-01-19 18:30:44

Judging History

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

  • [2024-01-19 18:30:44]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2024-01-19 18:30:44]
  • 提交

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 PI = acos(-1.0);
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);
}

ostream& operator<<(ostream& os, const Pt& p)
{
	return os << "(" << p.x << "," << p.y << ")";
}

struct Line
{
	Pt n;
	db c;
	Line (const Pt& _n, db _c): n(_n), c(_c) {}
	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;
}

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 {};
		Pt p = inter(l, d.back().F);
		if (SZ(d) < 2 || sgn(d.front().F.side(p)) >= 0)
		{
			if (!d.empty())
			{
				if (!parallel(l, d.front().F))
					d.front().S = inter(l, d.front().F);
			}
			d.PB({l, p});
		}
	}
	vector<Pt> res;
	for (const auto& [l, p] : d)
	{
		if (res.empty()
			|| sgn(sq(p - res.back())) > 0)
			res.PB(p);
	}
	return res;
}

db f(const vector<Pt>& v, db x0)
{
	int n = SZ(v), iMin = 0, iMax = 0;
	FOR(i, 0, SZ(v))
	{
		if (sgn(v[i].x - v[iMin].x) < 0)
			iMin = i;
		if (sgn(v[i].x - v[iMax].x) > 0)
			iMax = i;
	}
	vector pwx(3, vector<db>(n));
	FOR(i, 0, n)
	{
		pwx[0][i] = v[i].x * v[i].x;
		pwx[1][i] = pwx[0][i] * v[i].x;
		pwx[2][i] = pwx[1][i] * v[i].x;
	}
	db s0 = 0, s1 = 0, s2 = 0;
	for (int s : {-1, 1})
	{
		for (int i = iMin; i != iMax;)
		{
			int j = i - s;
			if (j < 0)
				j += n;
			if (j >= n)
				j -= n;
			db dx = v[j].x - v[i].x;
			if (sgn(dx) != 0)
			{
				db k = (v[j].y - v[i].y) / dx;
				db b = cross(v[j], v[i]) / dx;
				db dx2 = (pwx[0][j] - pwx[0][i]) / 2;
				db dx3 = (pwx[1][j] - pwx[1][i]) / 3;
				db dx4 = (pwx[2][j] - pwx[2][i]) / 4;
				s0 += s * (k * dx2 + b * dx);
				s1 += s * (k * dx3 + b * dx2);
				s2 += s * (k * dx4 + b * dx3);
			}
			i = j;
		}
	}
	return s2 - 2 * x0 * s1 + x0 * x0 * s0;
}

int main()
{
	ios::sync_with_stdio(0); 
	cin.tie(0);
	cout << fixed << setprecision(15);
	db xl, yl, xr, yr;
	int n;
	cin >> xl >> yl >> xr >> yr >> n;
	vector<Pt> v(n);
	for (Pt& p : v)
		cin >> p.x >> p.y;
	vector<Line> boundingLines =
		{{{0, 1}, -yl}, {{-1, 0}, xr},
			{{0, -1}, yr}, {{1, 0}, -xl}};
	vector<Line> linesOuter, linesInner;
	db ans = 0;
	FOR(i, 0, n)
	{
		linesOuter = boundingLines;
		linesInner = boundingLines;
		FOR(j, 0, n)
		{
			if (j == i)
				continue;
			Pt normal = v[j] - v[i];
			db c = -dot(normal, (v[i] + v[j]) / 2);
			linesOuter.PB({normal, c});
			linesInner.PB({normal * (-1), -c});
		}
		vector<Pt> vOuter = hplaneInter(linesOuter);
		vector<Pt> vInner = hplaneInter(linesInner);
		int s = 1;
		for (auto polygon : {vOuter, vInner})
		{
			ans += s * f(polygon, v[i].x);
			for (Pt& p : polygon)
				swap(p.x, p.y);
			reverse(ALL(polygon));
			ans += s * f(polygon, v[i].y);
			s *= -1;
		}
	}
	cout << PI * ans / ((xr - xl) * (yr - yl)) << "\n";
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Runtime Error

input:

0 0 2 2
2
3 1
1 3

output:


result: