QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#164010 | #6734. Click the Circle | ucup-team1209# | WA | 57ms | 3952kb | C++20 | 3.5kb | 2023-09-04 18:06:57 | 2023-09-04 18:06:57 |
Judging History
answer
#include<bits/stdc++.h>
using u64 = unsigned long long;
using std::cin;
using std::cout;
const int mod = 998244353;
const int N = 1e3 + 10;
using db = long double;
using vec2 = std::complex<db>;
using cp = vec2;
const db eps = 1e-9;
int n;
vec2 a[N], b[N];
struct line { vec2 a, b; };
db cross(const vec2 & x, const vec2 & y) {
return x.real() * y.imag() - x.imag() * y.real();
}
db dot(const vec2 & x, const vec2 & y) {
return x.real() * y.real() + x.imag() * y.imag();
}
db dist(line x, vec2 y) {
y -= x.a;
x.b -= x.a;
x.a -= x.a;
if(abs(x.b) < eps) return abs(y);
db prod = abs(x.b);
y /= x.b;
x.b = 1.;
db min = std::min(abs(y), abs(y - x.b));
if(0 <= y.real() && y.real() <= 1) {
min = std::min(min, std::abs(y.imag()));
}
return min * prod;
}
db sgn(db x) {
return x < -eps ? -1 : x > eps;
}
int ccw(vec2 a, vec2 b, vec2 c) {
int sign = sgn(cross(b - a, c - a));
if(sign == 0) {
if(sgn(dot(b - a, c - a)) == -1) return 2;
if(abs(c - a) > abs(b - a) + eps) return -2;
}
return sign;
}
bool isc(line x, line y) {
return ccw(x.a, x.b, y.a) * ccw(x.a, x.b, y.b) <= eps &&
ccw(y.a, y.b, x.a) * ccw(y.a, y.b, x.b) <= eps;
}
db dist(line x, line y) {
if(isc(x, y)) return 0;
db res = std::min({
dist(y, x.a), dist(y, x.b),
dist(x, y.a), dist(x, y.b),
});
return res;
}
db L[N], R[N];
db d, ra;
struct evt {
db l, r;
cp k, a;
};
std::vector<evt> v[N];
std::vector<evt> pb;
int main() {
if(0) {
line z(cp(0, 0), cp(0, 1));
line y(cp(1, 0), cp(1, 1));
cp o(0, 0);
cout << dist(y, o) << '\n';
}
std::ios::sync_with_stdio(false), cin.tie(0);
#ifdef zqj
freopen("4.in", "r", stdin);
#endif
cin >> n >> d >> ra;
for(int i = 1;i <= n;++i) {
int type;
db x, y, t;
cin >> type;
if(type == 1) {
cin >> x >> y >> t;
a[i] = cp(x, y);
b[i] = cp(x, y);
L[i] = R[i] = t;
v[i] = {evt{ L[i] - d, R[i] + d, cp(0, 0), a[i] }};
} else {
cin >> x >> y;
a[i] = cp(x, y);
cin >> x >> y;
b[i] = cp(x, y);
cin >> L[i] >> R[i];
cp k = (b[i] - a[i]) / (R[i] - L[i]);
v[i].push_back(evt{L[i] - d, L[i], cp(0, 0), a[i]});
v[i].push_back(evt{L[i], R[i], k, a[i] - k * L[i]});
v[i].push_back(evt{R[i], R[i] + d, cp(0, 0), b[i]});
pb.push_back({
L[i] - d,
R[i] + d,
a[i],
b[i]
});
}
}
int ans = 0;
for(int i = 1;i <= n;++i) {
for(int j = i + 1;j <= n;++j) {
int ok = 0;
for(auto x : v[i]) for(auto y : v[j]) {
db l = std::max(x.l, y.l);
db r = std::min(x.r, y.r);
if(l - eps <= r) {
cp kd = x.k - y.k;
cp ad = x.a - y.a;
line seg(kd * l + ad, kd * r + ad);
if(dist(seg, cp(0, 0)) <= ra * 2 + eps) {
ok = 1;
break;
}
}
}
if(ok) ans += 1;
}
}
for(int i = 1;i <= n;++i) {
for(auto x : pb) {
line ll(x.k, x.a);
int ok = 0;
for(auto y : v[i]) {
db l = std::max(x.l, y.l);
db r = std::min(x.r, y.r);
if(l - eps <= r) {
line seg(y.k * l + y.a, y.k * r + y.a);
if(dist(seg, ll) <= ra * 2 + eps) {
ok = 1;
break;
}
}
}
if(ok) ans += 1;
}
}
for(int i = 0;i < (int) pb.size();++i) {
for(int j = 0;j < i;++j) {
auto x = pb[i];
auto y = pb[j];
db l = std::max(x.l, y.l);
db r = std::min(x.r, y.r);
if(l - eps <= r) {
line ll(x.k, x.a);
line rr(y.k, y.a);
if(dist(ll, rr) <= ra * 2 + eps) {
ans += 1;
}
}
}
}
cout << ans << '\n';
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3652kb
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: 3588kb
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: 1ms
memory: 3604kb
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: 1ms
memory: 3592kb
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: 3644kb
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: 57ms
memory: 3952kb
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:
21112
result:
wrong answer 1st numbers differ - expected: '22721', found: '21112'