QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#368140 | #7803. H-Shaped Figures | Hjcc | WA | 3ms | 13480kb | C++20 | 2.8kb | 2024-03-26 21:07:15 | 2024-03-26 21:07:16 |
Judging History
answer
# include <bits/stdc++.h>
# define ll long long
using namespace std;
const int N = 2e5 + 5;
struct Dis {
ll x, y;
} P, Q;
struct Len {
Dis x, y;
Len (Dis X = {0, 0}, Dis Y = {0, 0}) {
x = X; y = Y;
}
} s[N];
int n;
Dis operator -(Dis x, Dis y) {
return {x.x - y.x, x.y - y.y};
}
ll operator *(Dis x, Dis y) {
return x.x * y.y - x.y * y.x;
}
ll operator *(Len x, Len y) {
return (x.y - x.x) * (y.y - y.x);
}
bool operator !=(Dis x, Dis y) {
return x.x != y.x || x.y != y.y;
}
vector<Dis> v[4];
int bit[N];
void add(int x, int v) {
for (; x <= n; x += x & -x) {
bit[x] += v;
}
}
int sum(int x) {
int v = 0;
for (; x; x -= x & -x) {
v += bit[x];
}
return v;
}
int f[N], r[N];
Dis c[N];
ll clc(vector<Dis> &x, vector<Dis> &y, Dis p, Dis q) {
int m = x.size() + y.size();
ll res = 0;
memset(bit, 0, sizeof(int) * (m + 1));
for (int i = 0; i < x.size(); i++) {
c[i] = x[i];
// cerr << x[i].x << ' ' << x[i].y << '\n';
}
// cerr << '\n';
for (int i = 0; i < y.size(); i++) {
c[i + x.size()] = y[i];
// cerr << y[i].x << ' ' << y[i].y << '\n';
}
// cerr << '\n';
// cerr << '\n';
for (int i = 0; i < m; i++) {
f[i] = i;
}
sort(f, f + m, [](int x, int y){
ll v = Len(P, c[x]) * Len(P, c[y]);
if (v == 0) {
return x < y;
}
return v > 0;
});
for (int i = 0; i < m; i++) {
r[f[i]] = i + 1;
}
sort(f, f + m, [](int x, int y){
ll v = Len(Q, c[x]) * Len(Q, c[y]);
if (v == 0) {
return x < y;
}
return v > 0;
});
for (int i = 0; i < m; i++) {
if (f[i] < x.size()) {
add(r[f[i]], 1);
} else {
res += sum(r[f[i]]);
}
}
// cerr << res << '\n';
return res;
}
void sov() {
cin >> P.x >> P.y >> Q.x >> Q.y;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> s[i].x.x >> s[i].x.y >> s[i].y.x >> s[i].y.y;
if (s[i].x != P && s[i].y != P && s[i].x != Q && s[i].y != Q && s[i] * Len(P, Q)) {
bool d = Len(P, Q) * Len(P, s[i].x) < 0;
if (s[i] * Len(P, s[i].x) == 0 && (Len(P, s[i].x) * Len(P, Q)) * (Len(P, s[i].y) * Len(P, Q)) < 0) {
v[d].push_back(s[i].x);
v[!d].push_back(s[i].y);
} else if (s[i] * Len(Q, s[i].x) == 0 && (Len(Q, s[i].x) * Len(Q, P)) * (Len(Q, s[i].y) * Len(Q, P)) < 0) {
v[d | 2].push_back(s[i].x);
v[!d | 2].push_back(s[i].y);
}
}
}
ll ans = v[0].size() * v[2].size();
ans -= clc(v[0], v[2], P, Q) + clc(v[3], v[1], Q, P);
cout << ans << '\n';
}
int main() {
# ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
# endif
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int T = 1;
cin >> T;
while (T--) {
sov();
}
}
详细
Test #1:
score: 100
Accepted
time: 3ms
memory: 13480kb
input:
1 0 0 4 0 8 0 0 2 1 -1 -1 2 2 3 3 5 -3 0 2 6 -1 2 -2 5 1 -1 1 3 -3 -1 0 2 0 -1 -1 2 2
output:
6
result:
ok 1 number(s): "6"
Test #2:
score: 0
Accepted
time: 2ms
memory: 10732kb
input:
1 -1 0 0 1 2 1 1 0 -1 1 1 0 1
output:
0
result:
ok 1 number(s): "0"
Test #3:
score: 0
Accepted
time: 0ms
memory: 11432kb
input:
1 5 -5 7 2 2 -6 8 2 6 -7 -10 -5 10
output:
0
result:
ok 1 number(s): "0"
Test #4:
score: 0
Accepted
time: 0ms
memory: 12356kb
input:
10 -4 7 -10 -4 3 -3 3 -6 -9 -9 -3 -6 -9 -7 0 6 5 0 -5 -3 5 5 -7 -3 -5 -6 6 1 -3 4 1 -4 -4 7 -2 9 3 8 -4 -3 9 0 -9 -3 7 8 25 4 6 4 5 4 -6 -9 -6 -8 -8 10 -6 6 4 2 -7 2 -5 10 -4 -1 -9 -2 -1 -9 -10 6 6 -5 1 -5 -2 -1 -10 -6 1 9 -9 0 -4 -2 -4 -1 3 2 5 -10 1 9 7 6 4 -2 -5 -4 -3 -3 -5 5 -8 3 0 -6 1 6 3 7 2 ...
output:
0 0 0 0 0 0 0 0 0 0
result:
ok 10 numbers
Test #5:
score: -100
Wrong Answer
time: 3ms
memory: 12956kb
input:
10 -3 7 1 9 285 9 -5 0 8 -3 0 -1 8 -6 -7 8 -10 -3 -8 9 2 -4 9 -8 4 6 -10 9 -2 -10 -5 -2 10 7 -10 -2 2 7 7 10 -5 7 8 -7 -1 2 4 7 -4 3 -10 -9 8 7 -7 6 -3 10 10 -6 -2 -2 7 -8 3 0 -10 -9 5 7 3 -3 7 6 -8 -5 6 8 -8 7 7 -9 -1 10 7 -10 6 -4 -1 -6 -10 -6 0 9 6 2 -9 0 6 -1 -1 0 2 6 0 -9 -8 6 -2 10 7 -7 -5 2 5...
output:
1 1 16 13 6 13 -2 14 9 21
result:
wrong answer 2nd numbers differ - expected: '0', found: '1'