QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#368140#7803. H-Shaped FiguresHjccWA 3ms13480kbC++202.8kb2024-03-26 21:07:152024-03-26 21:07:16

Judging History

你现在查看的是最新测评结果

  • [2024-03-26 21:07:16]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:13480kb
  • [2024-03-26 21:07:15]
  • 提交

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'