QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#407887#6734. Click the CircleyangshuyuWA 35ms4776kbC++145.5kb2024-05-09 14:03:152024-05-09 14:03:15

Judging History

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

  • [2024-05-09 14:03:15]
  • 评测
  • 测评结果:WA
  • 用时:35ms
  • 内存:4776kb
  • [2024-05-09 14:03:15]
  • 提交

answer

#include <bits/stdc++.h>
typedef long double var;
struct circle {
	public:
		int x, y, s, id;
};
struct segment {
	public:
		int sx, sy, tx, ty, s, t, id;
};
struct runcirc {
	public:
		int sx, sy, tx, ty, s, t, id;
};
std::vector<circle> c, nc;
std::vector<segment> s, ns;
std::vector<runcirc> q, nq;
int n, r, d, cnt;
var rr4;
std::bitset<5120> o[5120];
var sqrdist(var d, var dd, var ddd, var dddd) {
	return (d - ddd) * (d - ddd) + (dd - dddd) * (dd - dddd);
}
var sqrdist(var px, var py, var l1x, var l1y, var l2x, var l2y) {
	//	A=p-l1	B=l2-l1
	//	AB/|B|^2*B+l1
	var	bx = l2x - l1x, by = l2y - l1y, T = ((px - l1x) * bx + (py - l1y) * by) / (bx * bx + by * by),
			dx = T * bx + l1x, dy = T * by + l1y;
	if(((l1x <= dx && dx <= l2x) || (l2x <= dx && dx <= l1x)) && ((l1y <= dy && dy <= l2y) || (l2y <= dy && dy <= l1y)))
		return sqrdist(px, py, dx, dy);
	return std::min(sqrdist(px, py, l1x, l1y), sqrdist(px, py, l2x, l2y));
}
var cross(var p1x, var p1y, var p2x, var p2y) {
	return p1x * p2y - p2x * p1y;
}
int position(var px, var py, var l1x, var l1y, var l2x, var l2y) {
	var bx = l2x - l1x, by = l2y - l1y, cx = px - l1x, cy = py - l1y, S = cross(bx, by, cx, cy);
	if(std::max(S, -S) <= 1E-12L)
		if((bx * cx + by * cy) < 0)
			return 2;
		else if(((l1x <= px && px <= l2x) || (l2x <= px && px <= l1x)) && ((l1y <= py && py <= l2y) || (l2y <= py && py <= l1y)))
			return 4;
		else
			return 3;
	else
		return S > 0;
}
bool intersect(var l1x, var l1y, var l2x, var l2y, var l3x, var l3y, var l4x, var l4y) {
	int p1 = position(l1x, l1y, l3x, l3y, l4x, l4y),
		p2 = position(l2x, l2y, l3x, l3y, l4x, l4y),
		p3 = position(l3x, l3y, l1x, l1y, l2x, l2y),
		p4 = position(l4x, l4y, l1x, l1y, l2x, l2y);
	return ((p1 | p2 | p3 | p4) & 4) || (p1 != p2 && p3 != p4);
}
var sqrdist(var l1x, var l1y, var l2x, var l2y, var l3x, var l3y, var l4x, var l4y) {
	if(intersect(l1x, l1y, l2x, l2y, l3x, l3y, l4x, l4y))
		return 0;
	return std::min({
		sqrdist(l1x, l1y, l3x, l3y, l4x, l4y),
		sqrdist(l2x, l2y, l3x, l3y, l4x, l4y),
		sqrdist(l3x, l3y, l1x, l1y, l2x, l2y),
		sqrdist(l4x, l4y, l1x, l1y, l2x, l2y)
	});
}
int Abs(int y) {
	return std::max(y, -y);
}
int main() {
	scanf("%d%d%d", &n, &r, &d), rr4 = 4 * r * r + 1E-12L;
	for(int i = 1, op, q[8]; i <= n; i++) {
		scanf("%d", &op);
		if(op == 1)
			scanf("%d%d%d", q, q + 1, q + 2), cnt++,
			c.push_back(circle {q[0], q[1], q[2] - d, cnt}),
			c.push_back(circle {q[0], q[1], q[2], cnt});
		else if(op == 2)
			scanf("%d%d%d%d%d%d", q, q + 1, q + 2, q + 3, q + 4, q + 5), cnt++,
			c.push_back(circle {q[0], q[1], q[4] - d, cnt}),
			c.push_back(circle {q[2], q[3], q[5], cnt}),
			::q.push_back(runcirc {q[0], q[1], q[2], q[3], q[4], q[5], cnt}), cnt++,
			s.push_back(segment {q[0], q[1], q[2], q[3], q[4], q[5], cnt});
	//	printf("%d\n", cnt);
	}
	for(const circle &i : c) {
		for(const circle &j : c)
			o[i.id][j.id] = o[j.id][i.id] = o[i.id][j.id] || (Abs(i.s - j.s) <= d && sqrdist(i.x, i.y, j.x, j.y) < rr4);
		for(const segment &j : s)
			o[i.id][j.id] = o[j.id][i.id] = o[i.id][j.id] || (!(i.s + d < j.s || j.t < i.s) && sqrdist(i.x, i.y, j.sx, j.sy, j.tx, j.ty) < rr4);
		for(const runcirc &j : q)
			if(!(i.s + d < j.s || j.t < i.s)) {
				var L = std::max(i.s, j.s) - j.s, R = std::min(i.s + d, j.t) - j.s, O = j.t - j.s;
				L /= O, R /= O;
				o[i.id][j.id] = o[j.id][i.id] = o[i.id][j.id] || sqrdist(i.x, i.y,
					j.sx * L + j.tx * (1 - L), j.sy * L + j.ty * (1 - L),
					j.sx * R + j.tx * (1 - R), j.sy * R + j.ty * (1 - R)
				) < rr4;
			}
	}
	for(const segment &i : s) {
		for(const segment &j : s)
			o[i.id][j.id] = o[j.id][i.id] = o[i.id][j.id] || (!(i.t < j.s || j.t < i.s) && sqrdist(i.sx, i.sy, i.tx, i.ty, j.sx, j.sy, j.tx, j.ty) < rr4);
		for(const runcirc &j : q)
			if(!(i.t < j.s || j.t < i.s)) {
				var L = std::max(i.s, j.s) - j.s, R = std::min(i.t, j.t) - j.s, O = j.t - j.s;
				L /= O, R /= O;
				o[i.id][j.id] = o[j.id][i.id] = o[i.id][j.id] || sqrdist(i.sx, i.sy, i.tx, i.ty,
					j.sx * L + j.tx * (1 - L), j.sy * L + j.ty * (1 - L),
					j.sx * R + j.tx * (1 - R), j.sy * R + j.ty * (1 - R)
				) < rr4;
			}
	}
	for(const runcirc &i : q)
		for(const runcirc &j : q)
			if(!(i.t < j.s || j.t < i.s)) {
				var L = std::max(i.s, j.s), R = std::min(i.t, j.t), O = i.t - i.s, P = j.t - j.s;
				L -= i.s, R -= i.s;
				var	isx = i.sx * L + i.tx * (O - L), isy = i.sy * L + i.ty * (O - L),
						itx = i.sx * R + i.tx * (O - R), ity = i.sy * R + i.ty * (O - R);
				L += i.s, R += i.s, L -= j.s, R -= j.s;
				var	jsx = j.sx * L + j.tx * (P - L), jsy = j.sy * L + j.ty * (P - L),
						jtx = j.sx * R + j.tx * (P - R), jty = j.sy * R + j.ty * (P - R);
				L += j.s, R += j.s, isx /= O, isy /= O, itx /= O, ity /= O, jsx /= P, jsy /= P, jtx /= P, jty /= P;
				var	A = isx - jsx - itx + jtx, B = itx - jtx,
						C = isy - jsy - ity + jty, D = ity - jty;
				//	(AT+B)^2 + (CT+D)^2
				//	AATT + 2ABT + BB + CCTT + 2CDT + DD
				//	(AA+CC)TT + 2(AB+CD)T + (BB+DD)
				//	T in [0, 1]
				var E = A * A + C * C, F = 2 * (A * B + C * D), G = B * B + D * D;
				//	ET^2 + FT + G
				var K = std::max(E, -E) > 1E-12L ? -F / E / 2 : 114514;
				if(K < 0 || K > 1)
					o[i.id][j.id] = o[j.id][i.id] = o[i.id][j.id] || std::min(G, E + F + G) < rr4;
				else
					o[i.id][j.id] = o[j.id][i.id] = o[i.id][j.id] || K * K * E + K * F + G < rr4;
			}
	int res = 0;
	for(int i = 1; i <= cnt; i++)
		for(int j = i + 1; j <= cnt; j++)
			if(o[i][j])
			//	printf(" >> %d %d\n", i, j),
				res += o[i][j];
	printf("%d\n", res);
	return 0;
}

详细

Test #1:

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

input:

2 1 1
1 1 1 2
1 2 2 3

output:

1

result:

ok 1 number(s): "1"

Test #2:

score: 0
Accepted
time: 1ms
memory: 3804kb

input:

2 1 1
1 1 1 2
1 3 2 3

output:

0

result:

ok 1 number(s): "0"

Test #3:

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

input:

2 1 1
1 3 3 2
2 5 5 5 1 2 4

output:

3

result:

ok 1 number(s): "3"

Test #4:

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

input:

2 1 1
2 1 1 1 5 2 4
2 5 5 5 1 2 4

output:

2

result:

ok 1 number(s): "2"

Test #5:

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

input:

2 1 1
2 10 1 10 20 2 4
2 1 10 20 10 2 4

output:

6

result:

ok 1 number(s): "6"

Test #6:

score: -100
Wrong Answer
time: 35ms
memory: 4776kb

input:

1000 8 4
1 8323 2820 943
1 8246 2850 944
1 8177 2880 941
1 8154 2866 944
2 8325 8146 2865 2846 943 944
1 8349 2891 939
2 8176 8344 2888 2692 940 945
1 8191 2732 945
1 8144 2668 945
2 8182 8191 2889 2844 939 940
1 8173 2687 941
1 8241 2870 945
2 8266 8344 2910 2667 942 943
1 8169 2863 939
1 8349 2921...

output:

20663

result:

wrong answer 1st numbers differ - expected: '22721', found: '20663'