QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#290096#7783. Military ManeuverwillowWA 1029ms4680kbC++145.5kb2023-12-24 13:16:272023-12-24 13:16:27

Judging History

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

  • [2023-12-24 13:16:27]
  • 评测
  • 测评结果:WA
  • 用时:1029ms
  • 内存:4680kb
  • [2023-12-24 13:16:27]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const double eps = 1e-9, pi = acos(-1);
int Dcmp(double x) {
	return x < -eps ? -1 : x > eps ? 1 : 0;
}
struct Point {
	double x, y;
	Point(double x = 0, double y = 0) : x(x), y(y) {}
	Point operator + (Point rhs) {
		return Point(x + rhs.x, y + rhs.y);
	}
	Point operator - (Point rhs) {
		return Point(x - rhs.x, y - rhs.y);
	}
	double operator * (Point rhs) {
		return x * rhs.x + y * rhs.y;
	}
	double operator ^ (Point rhs) {
		return x * rhs.y - y * rhs.x;
	}
	Point operator * (double k) {
		return Point(x * k, y * k);
	}
	Point operator / (double k) {
		return Point(x / k, y / k);
	}
	Point Rotate90() {
		return Point(y, -x);
	}
	double len2() {
		return x * x + y * y;
	}
	double len() {
		return sqrt(len2());
	}
};
int Left(Point a, Point b, Point c) {
	return Dcmp((b - a) ^ (c - a)) >= 0;
}
Point base;
vector<Point> Convex(vector<Point>a) {
	int n = a.size(), cnt = 0;
	if(n < 3)
		return a;
	base = a[0];
	for(auto p : a)
		if(make_pair(p.x, p.y) < make_pair(base.x, base.y))
			base = p;
	sort(a.begin(), a.end(), [](Point a, Point b) {
		int d = Dcmp((a - base) ^ (b - base));
		if(d)
			return d > 0;
		return (a - base).len() < (b - base).len();
	});
	vector<Point>res;
	for(int i = 0; i < n; ++ i) {
		while(cnt > 1 && Left(res[cnt - 2], a[i], res[cnt - 1]))
			-- cnt, res.pop_back();
		res.push_back(a[i]), ++ cnt;
	}
	return res;
}
struct Line {
	Point s, t;
	Line(Point s = Point(), Point t = Point()) : s(s), t(t) {}
};
bool OnLeft(Line l, Point p) {
	return Left(l.s, l.t, p);
}
Point LineInter(Line l1, Line l2) {
// cerr << "Inter: " << endl;
// cerr << "(" << l1.s.x << ", " << l1.s.y << ") -- (" << l1.t.x << ", " << l1.t.y << ")" << endl;
// cerr << "(" << l2.s.x << ", " << l2.s.y << ") -- (" << l2.t.x << ", " << l2.t.y << ")" << endl;
	double a1 = (l2.t - l2.s) ^ (l1.s - l2.s), a2 = (l2.t - l2.s) ^ (l1.t - l2.s);
	return (l1.s * a2 - l1.t * a1) / (a2 - a1);
}
Line Middle(Point s, Point t) {
	Point p = (s + t) / 2, v = (t - s).Rotate90();
	assert(Left(p, p - v, s));
	return Line(p, p - v);
}
vector<Point> Intersect(vector<Line> h) {
	typedef pair<double, Line> polar;
	vector<polar> g;
	for(auto l : h) {
		Point v = l.t - l.s;
		g.push_back(make_pair(atan2(v.y, v.x), l));
	}
	sort(g.begin(), g.end(), [] (polar a, polar b) {
		if(Dcmp(a.first - b.first) == 0)
			return Dcmp((a.second.t - a.second.s) ^ (b.second.t - b.second.s)) < 0;
		return Dcmp(a.first - b.first) < 0;
	});
	h.resize(unique(g.begin(), g.end(), [] (polar a, polar b) {
		return Dcmp(a.first - b.first) == 0;
	}) - g.begin());
	for(int i = 0; i < (int)h.size(); ++ i)
		h[i] = g[i].second;
	int fore = 0, rear = -1;
	vector<Line> ret;
	ret.clear();
	for(int i = 0; i < (int)h.size(); ++ i) {
		while(fore < rear && !OnLeft(h[i], LineInter(ret[rear - 1], ret[rear])))
			-- rear, ret.pop_back();
		while(fore < rear && !OnLeft(h[i], LineInter(ret[fore], ret[fore + 1])))
			++ fore;
		++ rear, ret.push_back(h[i]);
	}
	while(rear - fore > 1 && !OnLeft(ret[fore], LineInter(ret[rear - 1], ret[rear])))
		-- rear, ret.pop_back();
	while(rear - fore > 1 && !OnLeft(ret[rear], LineInter(ret[fore], ret[fore + 1])))
		++ fore;
	if(rear - fore < 2)
		return vector<Point>();
	vector<Point> ans;
	ans.resize(rear - fore + 1);
	for(int i = 0; i < (int)ans.size(); ++ i)
		ans[i] = LineInter(ret[fore + i], ret[fore + (i + 1) % ans.size()]);
	return ans;
}
const int maxn = 2005, inf = 2e4;
int xl, yl, xr, yr, n;
Point p[maxn];
double ans;
void Calc(vector<Point> poly, Point p, int coef) {
	int n = (int)poly.size();
	double area = 0;
	for(int i = 0; i < n; ++ i) {
		area += poly[i] ^ poly[(i + 1) % n];
	}
	area /= 2;
	ans += area * p.len2() * coef;
	double sx = 0, sy = 0;
	for(int i = 0; i < n; ++ i) {
		Point p1 = poly[i], p2 = poly[(i + 1) % n];
		sx += (p1.x + p2.x) * (p1 ^ p2);
		sy += (p1.y + p2.y) * (p1 ^ p2);
	}
	sx /= 6, sy /= 6;
	ans -= sx * (2 * p.x) * coef;
	ans -= sy * (2 * p.y) * coef;
}
int main() {
	scanf("%d%d%d%d", &xl, &yl, &xr, &yr);
	scanf("%d", &n);
	for(int i = 1, x, y; i <= n; ++ i) {
		scanf("%d%d", &x, &y);
		p[i] = Point(x, y);
	}
	for(int i = 1; i <= n; ++ i) {
		vector<Line> vl;
		vl.clear();
		vl.push_back(Line(Point(xl, inf), Point(xl, -inf)));
		vl.push_back(Line(Point(-inf, yl), Point(inf, yl)));
		vl.push_back(Line(Point(xr, -inf), Point(xr, inf)));
		vl.push_back(Line(Point(inf, yr), Point(-inf, yr)));
		for(int j = 1; j <= n; ++ j) {
			if(i != j) {
				vl.push_back(Middle(p[j], p[i]));
			}
		}
		auto vp = Convex(Intersect(vl));
		if(!vp.size())
			continue;
// cerr << "Point(" << p[i].x << ", " << p[i].y << "): ";
// for(auto p : vp)
// 	cerr << p.x << " " << p.y << endl;
// cerr << endl;
		Calc(vp, p[i], 1);
	}
// cerr << ans << endl;
	for(int i = 1; i <= n; ++ i) {
		vector<Line> vl;
		vl.clear();
		vl.push_back(Line(Point(xl, inf), Point(xl, -inf)));
		vl.push_back(Line(Point(-inf, yl), Point(inf, yl)));
		vl.push_back(Line(Point(xr, -inf), Point(xr, inf)));
		vl.push_back(Line(Point(inf, yr), Point(-inf, yr)));
		for(int j = 1; j <= n; ++ j) {
			if(i != j) {
				vl.push_back(Middle(p[i], p[j]));
			}
		}
		auto vp = Convex(Intersect(vl));
		if(!vp.size())
			continue;
// cerr << "Point(" << p[i].x << ", " << p[i].y << "): ";
// for(auto p : vp)
// 	cerr << p.x << " " << p.y << endl;
// cerr << endl;
		Calc(vp, p[i], -1);
	}
// cerr << ans << endl;
	ans /= (xr - xl) * (yr - yl);
	printf("%.15f\n", ans * pi);
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

0 0 2 2
2
3 1
1 3

output:

8.377580409572779

result:

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

Test #2:

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

input:

0 0 2 2
2
5 1
1 3

output:

37.699111843077517

result:

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

Test #3:

score: -100
Wrong Answer
time: 1029ms
memory: 4680kb

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:

11260841.620147660374641

result:

wrong answer 1st numbers differ - expected: '6657168.1428534', found: '11260841.6201477', error = '0.6915363'