QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#125230 | #6734. Click the Circle | hos_lyric | WA | 7ms | 3840kb | C++14 | 7.7kb | 2023-07-16 07:54:46 | 2023-07-16 07:54:50 |
Judging History
answer
#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
using Int = long long;
template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
int sig(Int r) { return (r < 0) ? -1 : (r > 0) ? +1 : 0; }
struct Pt {
Int x, y;
Pt() : x(0), y(0) {}
Pt(Int x_, Int y_) : x(x_), y(y_) {}
Pt operator+(const Pt &a) const { return Pt(x + a.x, y + a.y); }
Pt operator-(const Pt &a) const { return Pt(x - a.x, y - a.y); }
Pt operator*(const Pt &a) const { return Pt(x * a.x - y * a.y, x * a.y + y * a.x); }
Pt operator+() const { return Pt(+x, +y); }
Pt operator-() const { return Pt(-x, -y); }
Pt operator*(const Int &k) const { return Pt(x * k, y * k); }
Pt operator/(const Int &k) const { return Pt(x / k, y / k); }
friend Pt operator*(const Int &k, const Pt &a) { return Pt(k * a.x, k * a.y); }
Pt &operator+=(const Pt &a) { x += a.x; y += a.y; return *this; }
Pt &operator-=(const Pt &a) { x -= a.x; y -= a.y; return *this; }
Pt &operator*=(const Pt &a) { return *this = *this * a; }
Pt &operator*=(const Int &k) { x *= k; y *= k; return *this; }
Int abs2() const { return x * x + y * y; }
Int dot(const Pt &a) const { return x * a.x + y * a.y; }
Int det(const Pt &a) const { return x * a.y - y * a.x; }
bool operator==(const Pt &a) const { return (x == a.x && y == a.y); }
bool operator<(const Pt &a) const { return (x < a.x || (x == a.x && y < a.y)); }
friend ostream &operator<<(ostream &os, const Pt &a) { os << "(" << a.x << ", " << a.y << ")"; return os; }
};
Int tri(const Pt &a, const Pt &b, const Pt &c) { return (b - a).det(c - a); }
// Watch out for the case a == b.
int iSP(const Pt &a, const Pt &b, const Pt &c) {
int s = sig((b - a).det(c - a));
if (s) return s;
if (sig((b - a).dot(c - a)) < 0) return -2; // c-a-b
if (sig((a - b).dot(c - b)) < 0) return +2; // a-b-c
return 0;
}
// Watch out for the case a == b || c == d.
bool iSS(const Pt &a, const Pt &b, const Pt &c, const Pt &d) {
return (iSP(a, b, c) * iSP(a, b, d) <= 0 && iSP(c, d, a) * iSP(c, d, b) <= 0);
}
int N;
Int R, W;
vector<int> O;
vector<Pt> C, D;
vector<Int> U, V;
struct Info {
int len;
Int ts[4];
Pt ps[4];
};
bool dSP2(const Pt &a, const Pt &b, const Pt &c) {
if ((b - a).dot(c - a) <= 0) return (c - a).abs2() <=4*R*R;
if ((a - b).dot(c - b) <= 0) return (c - b).abs2() <=4*R*R;
// return abs(tri(a, b, c)) / (b - a).abs();
// cerr<<" HELP "<<tri(a, b, c)<<" "<<(b - a).abs2()<<endl;
return tri(a, b, c) * tri(a, b, c) <= 4*R*R * (b - a).abs2();
}
bool dSS2(const Pt &a, const Pt &b, const Pt &c, const Pt &d) {
return iSS(a, b, c, d) ? true : max(max(dSP2(a, b, c), dSP2(a, b, d)), max(dSP2(c, d, a), dSP2(c, d, b)));
}
bool solve(const Pt c0, const Pt &u0, Int d0, const Pt &c1, const Pt &u1, Int d1, Int tL, Int tR) {
// cerr<<" solve "<<c0<<" "<<u0<<" "<<d0<<" "<<c1<<" "<<u1<<" "<<d1<<" "<<tL<<" "<<tR<<endl;
__int128 tar = 4*R*R;
tar *= d0*d0;
tar *= d1*d1;
const Pt o = d0 * c1 - d1 * c0;
const Pt u = d0 * u1 - d1 * u0;
// a t^2 + 2 b t + c <= 0
__int128 a = (__int128)u.x * u.x + (__int128)u.y * u.y;
__int128 b = (__int128)u.x * o.x + (__int128)u.y * o.y;
__int128 c = (__int128)o.x * o.x + (__int128)o.y * o.y;
c -= tar;
if ((a * tL + 2*b) * tL + c <= 0) return true;
if ((a * tR + 2*b) * tR + c <= 0) return true;
if (a > 0 && b*b - a*c >= 0 && a*tL <= -b && -b <= a*tR) return true;
return false;
}
bool segseg(const Pt &a, const Pt &b, const Pt &c, const Pt &d) {
// cerr<<" segseg "<<a<<" "<<b<<" "<<c<<" "<<d<<endl;
if (a == b && c == d) {
return ((c - a).abs2() <= 4*R*R);
} else if (a == b) {
return dSP2(c, d, a);
} else if (c == d) {
return dSP2(a, b, c);
} else {
return dSS2(a, b, c, d);
}
}
bool circir(const Info &c0, const Info &c1) {
for (int i0 = 0; i0 < c0.len; ++i0) for (int i1 = 0; i1 < c1.len; ++i1) {
const Int tL = max(c0.ts[i0], c1.ts[i1]);
const Int tR = min(c0.ts[i0 + 1], c1.ts[i1 + 1]);
if (tL <= tR) {
// cerr<<" help "<<i0<<" "<<i1<<" "<<tL<<" "<<tR<<endl;
const Int d0 = c0.ts[i0 + 1] - c0.ts[i0];
const Int d1 = c1.ts[i1 + 1] - c1.ts[i1];
const Pt u0 = c0.ps[i0 + 1] - c0.ps[i0];
const Pt u1 = c1.ps[i1 + 1] - c1.ps[i1];
if (solve(
d0 * c0.ps[i0] - c0.ts[i0] * u0, u0, d0,
d1 * c1.ps[i1] - c1.ts[i1] * u1, u1, d1,
tL, tR)) {
return true;
}
}
}
return false;
}
bool fracir(const Info &f, const Info &c) {
if (max(f.ts[0], c.ts[0]) <= min(f.ts[1], c.ts[c.len])) {
if (segseg(f.ps[0], f.ps[1], c.ps[0], c.ps[c.len])) {
return true;
}
}
return false;
}
bool frafra(const Info &f0, const Info &f1) {
if (max(f0.ts[0], f1.ts[0]) <= min(f0.ts[1], f1.ts[1])) {
if (segseg(f0.ps[0], f0.ps[1], f1.ps[0], f1.ps[1])) {
return true;
}
}
return false;
}
int main() {
for (; ~scanf("%d%lld%lld", &N, &R, &W); ) {
O.resize(N);
C.resize(N);
D.resize(N);
U.resize(N);
V.resize(N);
for (int i = 0; i < N; ++i) {
scanf("%d", &O[i]);
if (O[i] == 1) {
scanf("%lld%lld%lld", &C[i].x, &C[i].y, &U[i]);
} else {
scanf("%lld%lld%lld%lld%lld%lld", &C[i].x, &C[i].y, &D[i].x, &D[i].y, &U[i], &V[i]);
}
}
vector<Info> circles, frames;
for (int i = 0; i < N; ++i) {
if (O[i] == 1) {
Info c;
c.len = 1;
c.ts[0] = U[i] - W;
c.ts[1] = U[i] + W;
c.ps[0] = C[i];
c.ps[1] = C[i];
circles.push_back(c);
} else {
Info c, f;
c.len = 3;
c.ts[0] = U[i] - W;
c.ts[1] = U[i];
c.ts[2] = V[i];
c.ts[3] = V[i] + W;
c.ps[0] = C[i];
c.ps[1] = C[i];
c.ps[2] = D[i];
c.ps[3] = D[i];
circles.push_back(c);
f.len = 1;
f.ts[0] = U[i] - W;
f.ts[1] = V[i] + W;
f.ps[0] = C[i];
f.ps[1] = D[i];
frames.push_back(f);
}
}
int ans = 0;
for (int i = 0; i < (int)circles.size(); ++i) for (int j = i + 1; j < (int)circles.size(); ++j) {
if (circir(circles[i], circles[j])) {
// cerr<<"circir "<<i<<" "<<j<<endl;
++ans;
}
}
for (int i = 0; i < (int)frames.size(); ++i) for (int j = 0; j < (int)circles.size(); ++j) {
if (fracir(frames[i], circles[j])) {
// cerr<<"fracir "<<i<<" "<<j<<endl;
++ans;
}
}
for (int i = 0; i < (int)frames.size(); ++i) for (int j = i + 1; j < (int)frames.size(); ++j) {
if (frafra(frames[i], frames[j])) {
// cerr<<"frafra "<<i<<" "<<j<<endl;
++ans;
}
}
printf("%d\n", ans);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
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: 3656kb
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: 3656kb
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: 3640kb
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: 3648kb
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: 7ms
memory: 3840kb
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:
28635
result:
wrong answer 1st numbers differ - expected: '22721', found: '28635'