QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#129882 | #6734. Click the Circle | UndertrainedOverpressure | WA | 26ms | 3648kb | C++23 | 7.0kb | 2023-07-23 02:29:56 | 2023-07-23 02:29:58 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define TIME (clock() * 1.0 / CLOCKS_PER_SEC)
// _________ vect (2D) ______________
template <typename T>
struct vect {
T x = 0;
T y = 0;
vect() = default;
vect(T x_, T y_) : x(x_), y(y_) {}
inline T len2() const {
return x * x + y * y;
}
inline ld len() const {
return sqrtl(len2());
}
inline vect rotate() const {
return vect(-y, x);
}
};
template <typename T>
inline istream& operator>>(istream& in, vect<T>& v) {
return in >> v.x >> v.y;
}
template <typename T>
inline ostream& operator<<(ostream& out, const vect<T>& v) {
return out << "[" << v.x << "," << v.y << "]";
}
template <typename T>
inline vect<T> operator+(const vect<T>& a, const vect<T>& b) {
return vect(a.x + b.x, a.y + b.y);
}
template <typename T>
inline vect<T> operator-(const vect<T>& a, const vect<T>& b) {
return vect(a.x - b.x, a.y - b.y);
}
template <typename T>
inline vect<T> operator*(const vect<T>& a, T k) {
return vect(a.x * k, a.y * k);
}
template <typename T>
inline T operator*(const vect<T>& a, const vect<T>& b) {
return a.x * b.x + a.y * b.y;
}
template <typename T>
inline T operator^(const vect<T>& a, const vect<T>& b) {
return a.x * b.y - a.y * b.x;
}
template <typename T>
inline bool operator==(const vect<T>& a, const vect<T>& b) {
return a.x == b.x && a.y == b.y;
}
struct tubus {
vect<ll> a, b;
int L, R;
tubus(vect<ll> a, vect<ll> b, int L, int R) : a(a), b(b), L(L), R(R) {}
};
__int128 abs(__int128 x) {
if (x < 0) {
return -x;
}
return x;
}
bool check(vect<__int128> a, vect<__int128> b, vect<__int128> c, __int128 r) {
if (b == c) {
return (a - b).len2() <= r * r;
}
__int128 mn = min((a - b).len2(), (a - c).len2());
if (((a - b) * (c - b)) <= 0 || ((a - c) * (b - c)) <= 0) {
return mn <= r * r;
}
__int128 area = abs((b - a) ^ (c - a));
assert(area <= (__int128)(1e19));
assert((b - c).len2() <= (__int128)(1e19));
assert(r * r <= (__int128)(1e19));
return area * area <= (b - c).len2() * r * r;
}
bool on_seg(vect<__int128> a, vect<__int128> b, vect<__int128> c) {
return ((a - c) ^ (b - c)) == 0 && ((a - c) * (b - c)) <= 0;
}
int sign(__int128 x) {
if (x < 0) {
return -1;
}
if (x == 0) {
return 0;
}
return 1;
}
bool check(vect<ll> aa, vect<ll> bb, vect<ll> cc, vect<ll> dd, __int128 r) {
vect<__int128> a(aa.x, aa.y);
vect<__int128> b(bb.x, bb.y);
vect<__int128> c(cc.x, cc.y);
vect<__int128> d(dd.x, dd.y);
if (a == b) {
return check(a, c, d, r);
}
if (c == d) {
return check(c, a, b, r);
}
if (on_seg(a, b, c) || on_seg(a, b, d) || on_seg(c, d, a) || on_seg(c, d, b)) {
return true;
}
if (((a - c) ^ (b - c)) == 0) {
return false;
}
if (((a - d) ^ (b - d)) == 0) {
return false;
}
if (((c - a) ^ (d - a)) == 0) {
return false;
}
if (((c - b) ^ (d - b)) == 0) {
return false;
}
if (sign((c - a) ^ (d - a)) != sign((c - b) ^ (d - b)) && sign((a - c) ^ (b - c)) != sign((a - d) ^ (b - d))) {
return true;
}
return check(a, c, d, r) || check(b, c, d, r) || check(c, a, b, r) || check(d, a, b, r);
}
bool check_tb_tb(tubus t1, tubus t2, int r) {
if (t1.R < t2.L || t2.R < t1.L) {
return false;
}
return check(t1.a, t1.b, t2.a, t2.b, r);
}
bool check_tb_run(tubus t1, tubus t2, ll r, int d) {
if (check_tb_tb(t1, tubus(t2.a, t2.a, t2.L - d, t2.L), r)) {
return true;
}
if (check_tb_tb(t1, tubus(t2.b, t2.b, t2.R, t2.R + d), r)) {
return true;
}
int seg_l = max(t1.L, t2.L);
int seg_r = min(t1.R, t2.R);
if (seg_l > seg_r) {
return false;
}
r *= (ll)(t2.R - t2.L);
t1.a = t1.a * (ll)(t2.R - t2.L);
t1.b = t1.b * (ll)(t2.R - t2.L);
//t2.a = t2.a * (ll)(t2.R - t2.L);
//t2.b = t2.b * (ll)(t2.R - t2.L);
auto new_a = t2.a * (ll)(t2.R - seg_l) + t2.b * (ll)(seg_l - t2.L);
auto new_b = t2.a * (ll)(t2.R - seg_r) + t2.b * (ll)(seg_r - t2.L);
t2.a = new_a;
t2.b = new_b;
return check(t1.a, t1.b, t2.a, t2.b, r);
}
bool check_run_run(tubus t1, tubus t2, ll r, int d) {
if (check_tb_run(tubus(t1.a, t1.a, t1.L - d, t1.L), t2, r, d)) {
return true;
}
if (check_tb_run(tubus(t1.b, t1.b, t1.R, t1.R + d), t2, r, d)) {
return true;
}
if (check_tb_run(tubus(t2.a, t2.a, t2.L - d, t2.L), t1, r, d)) {
return true;
}
if (check_tb_run(tubus(t2.b, t2.b, t2.R, t2.R + d), t1, r, d)) {
return true;
}
int seg_l = max(t1.L, t2.L);
int seg_r = min(t1.R, t2.R);
if (seg_l > seg_r) {
return false;
}
r *= (ll)(t2.R - t2.L) * (ll)(t1.R - t1.L);
t1.a = t1.a * (ll)(t2.R - t2.L);
t1.b = t1.b * (ll)(t2.R - t2.L);
t2.a = t2.a * (ll)(t1.R - t1.L);
t2.b = t2.b * (ll)(t1.R - t1.L);
{
auto new_a = t2.a * (ll)(t2.R - seg_l) + t2.b * (ll)(seg_l - t2.L);
auto new_b = t2.a * (ll)(t2.R - seg_r) + t2.b * (ll)(seg_r - t2.L);
t2.a = new_a;
t2.b = new_b;
}
{
auto new_a = t1.a * (ll)(t1.R - seg_l) + t1.b * (ll)(seg_l - t1.L);
auto new_b = t1.a * (ll)(t1.R - seg_r) + t1.b * (ll)(seg_r - t1.L);
t1.a = new_a;
t1.b = new_b;
}
return check(vect<ll>(), vect<ll>(), t2.a - t1.a, t2.b - t1.b, r);
}
void solve() {
int n, r, d;
cin >> n >> r >> d;
r *= 2;
vector<tubus> tb, run;
for (int i = 0; i < n; i++) {
int type;
cin >> type;
if (type == 1) {
vect<ll> c;
int t;
cin >> c >> t;
tb.emplace_back(c, c, t - d, t + d);
} else {
vect<ll> c, s;
int u, v;
cin >> c >> s >> u >> v;
tb.emplace_back(c, s, u - d, v + d);
run.emplace_back(c, s, u, v);
}
}
int ans = 0;
for (int i = 0; i < tb.size(); i++) {
for (int j = i + 1; j < tb.size(); j++) {
if (check_tb_tb(tb[i], tb[j], r)) {
ans++;
}
}
}
for (int i = 0; i < tb.size(); i++) {
for (int j = 0; j < run.size(); j++) {
if (check_tb_run(tb[i], run[j], r, d)) {
ans++;
}
}
}
for (int i = 0; i < run.size(); i++) {
for (int j = i + 1; j < run.size(); j++) {
if (check_run_run(run[i], run[j], r, d)) {
ans++;
}
}
}
cout << ans << "\n";
}
int main() {
#ifdef ONPC
freopen("input", "r", stdin);
#endif
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int t = 1;
//cin >> t;
while (t--) {
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3468kb
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: 3532kb
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: 3528kb
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: 3508kb
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: 26ms
memory: 3648kb
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:
22709
result:
wrong answer 1st numbers differ - expected: '22721', found: '22709'