QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#407884 | #6734. Click the Circle | yangshuyu | WA | 36ms | 4896kb | C++14 | 5.6kb | 2024-05-09 14:01:54 | 2024-05-09 14:01:55 |
Judging History
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==114514) o[i.id][j.id]=o[j.id][i.id]=1;
else 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: 3904kb
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: 0ms
memory: 3704kb
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: 3860kb
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: 3880kb
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: 1ms
memory: 3852kb
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: 36ms
memory: 4896kb
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:
21001
result:
wrong answer 1st numbers differ - expected: '22721', found: '21001'