QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#67522#2676. 鱼alpha1022100 ✓420ms10368kbC++203.4kb2022-12-10 16:55:542022-12-10 16:55:57

Judging History

This is the latest submission verdict.

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-12-10 16:55:57]
  • Judged
  • Verdict: 100
  • Time: 420ms
  • Memory: 10368kb
  • [2022-12-10 16:55:54]
  • Submitted

answer

#include <cmath>
#include <cstdio>
#include <utility>
#include <algorithm>
using namespace std;
const int N = 1e3;
const double pi = acos(-1);
const double eps = 1e-13;
int n;
struct point {
  long long x, y, dis;
  int id;
  inline point(long long a = 0, long long b = 0, int c = 0) {
    x = a, y = b, id = c;
  }
  inline point operator+(const point &o) const {
    return point(x + o.x, y + o.y);
  }
  inline point operator-(const point &o) const {
    return point(x - o.x, y - o.y);
  }
  inline point operator*(const int &v) const {
    return point(x * v, y * v);
  }
  inline long long operator*(const point &o) const {
    return x * o.y - y * o.x;
  }
  inline bool operator<(const point &o) const {
    return dis < o.dis;
  }
  inline double angle() const {
    return atan2(y, x);
  }
} a[N + 5], t[N + 5];
inline long long dis(const point &a, const point &b) {
  return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}
int cnt[N + 5][N + 5][2];
pair<double, int> s[N * N + 5];
int tot;
long long ans;
inline long long calc(const double &L, const double &R) {
  return (upper_bound(s + 1, s + tot + 1, make_pair(R, 0x3f3f3f3f)) - 1)->second - (lower_bound(s + 1,
         s + tot + 1, make_pair(L, -0x3f3f3f3f)) - 1)->second;
}
int main() {
  scanf("%d", &n);
  for (register int i = 1; i <= n; ++i)
    scanf("%lld%lld", &a[i].x, &a[i].y), a[i].id = i, t[i] = a[i];
  for (register int i = 1; i <= n; ++i) {
    for (register int j = 1; j <= n; ++j)
      t[j].dis = dis(t[j], a[i]);
    sort(t + 1, t + n + 1);
    for (register int l = 1, r; l <= n; l = r + 1) {
      for (r = l; r < n && dis(t[r + 1], a[i]) == dis(t[l], a[i]); ++r);
      for (register int j = l; j <= r; ++j)
        for (register int k = j + 1; k <= r; ++k) {
          long long crs = (t[k] - t[j]) * (a[i] - t[j]);
          if (crs)
            ++cnt[t[j].id][t[k].id][crs > 0], ++cnt[t[k].id][t[j].id][crs < 0];
        }
    }
  }
  for (register int i = 1; i <= n; ++i) {
    for (register int j = 1; j <= n; ++j)
      t[j].dis = dis(t[j], a[i]);
    sort(t + 1, t + n + 1), tot = 0;
    for (register int l = 1, r; l <= n; l = r + 1) {
      for (r = l; r < n && dis(t[r + 1], a[i]) == dis(t[l], a[i]); ++r);
      for (register int j = l; j <= r; ++j)
        for (register int k = j + 1; k <= r; ++k) {
          long long crs = (t[k] - t[j]) * (a[i] - t[j]);
          if (crs)
            s[++tot] = make_pair((t[j] + t[k] - a[i] * 2).angle(), cnt[t[j].id][t[k].id][crs < 0]);
        }
    }
    sort(s + 1, s + tot + 1);
    for (register int i = 1; i <= tot; ++i)
      s[i].second += s[i - 1].second;
    for (register int l = 1, r; l <= n; l = r + 1) {
      for (r = l; r < n && dis(t[r + 1], a[i]) == dis(t[l], a[i]); ++r);
      for (register int j = l; j <= r; ++j)
        for (register int k = j + 1; k <= r; ++k) {
          long long crs = (t[k] - t[j]) * (a[i] - t[j]);
          if (crs) {
            int x = j, y = k;
            (t[y] - a[i]) * (t[x] - a[i]) > 0 && (swap(x, y), 1);
            double L = (t[y] - a[i]).angle() + pi / 2, R = (t[x] - a[i]).angle() + pi * 3 / 2;
            L > pi &&(L -= 2 * pi), R > pi && (R -= 2 * pi);
            if (L < R)
              ans += calc(L + eps, R - eps);
            else
              ans += calc(L + eps, pi) + calc(-pi, R - eps);
          }
        }
    }
  }
  ans <<= 2;
  printf("%lld\n", ans);
}

詳細信息

Test #1:

score: 10
Accepted
time: 0ms
memory: 4412kb

input:

10
0 -1
0 1
-1 0
1 0
1 2
1 -2
2 1
2 0
2 -1
3 0

output:

16

result:

ok 1 number(s): "16"

Test #2:

score: 10
Accepted
time: 2ms
memory: 4432kb

input:

10
0 -1
2 -2
-3 2
-1 2
2 3
1 -3
-2 0
2 -1
-1 1
0 -3

output:

12

result:

ok 1 number(s): "12"

Test #3:

score: 10
Accepted
time: 32ms
memory: 5584kb

input:

300
1607 14546
-11329 -3241
-12946 16163
16160 -9709
14543 -16177
14543 -4858
-9712 3227
-9712 11312
-8095 12929
9692 -14560
-6478 -12943
-1627 12929
9692 11312
-4861 -16177
-11329 11312
8075 -6475
-8095 -11326
-10 -7
8075 9695
-4861 16163
-9712 -14560
-8095 3227
14543 -1624
-9712 6461
11309 8078
16...

output:

48043376

result:

ok 1 number(s): "48043376"

Test #4:

score: 10
Accepted
time: 15ms
memory: 4024kb

input:

300
-88030 93
32128 809
-29829 -11382
82333 93
30966 -8487
-15617 28024
10166 30513
91 48905
-60931 61115
-7168 -31119
-3666 -31731
91 66148
-31809 3138
-31577 -4808
-13481 -28936
11566 30013
31991 3138
77295 77297
-31925 -1270
-63447 -63445
95502 95504
31208 7749
-9984 30513
31208 -7563
30011 -1138...

output:

101425104

result:

ok 1 number(s): "101425104"

Test #5:

score: 10
Accepted
time: 420ms
memory: 10368kb

input:

1000
-1 -11
-15 -10
-6 -12
-15 5
-18 6
0 -5
-15 -12
-5 14
-5 7
-14 -10
-9 14
8 -20
2 -5
1 9
14 -6
-10 -17
0 -3
-18 -18
0 3
-11 15
-5 -14
9 18
6 4
-8 -3
-1 -18
8 -8
18 20
-20 9
-11 6
-1 14
-7 -7
18 9
-7 -12
5 11
-13 14
10 12
5 -4
16 -17
2 6
8 6
-7 0
-17 3
9 9
-14 -12
-2 7
-19 11
-7 -18
-11 4
-6 -16
1...

output:

3667555924

result:

ok 1 number(s): "3667555924"

Test #6:

score: 10
Accepted
time: 416ms
memory: 10248kb

input:

1000
-18 -5
10 -12
5 3
-6 20
14 -12
-9 -1
5 -9
-2 7
6 0
-7 -16
-11 4
3 -5
-6 7
-18 -1
-14 -6
17 11
6 -14
-7 4
-7 -7
-10 11
18 13
-9 1
-18 -11
-16 -13
-5 4
-15 -4
10 -19
11 4
18 -1
7 20
12 6
-1 18
7 17
-16 -12
-3 5
-13 -14
9 13
-6 -6
4 9
-4 17
12 -14
19 2
4 -1
9 -19
-2 2
20 -11
-16 -20
-11 3
15 -14
-...

output:

3587138736

result:

ok 1 number(s): "3587138736"

Test #7:

score: 10
Accepted
time: 128ms
memory: 9612kb

input:

1000
-663306871 -774108750
520145821 -8
-246072173 -246072096
606233562 0
15640 37732
-46092226 -46092149
-323272042 -8
165336426 275560710
-27200 -30608
-692496701 400149319
-826682130 -661345704
-220448568 606233562
9979 39619
-85 -209956649
771569988 -220448568
551121420 826682130
55112142 -66134...

output:

793715188

result:

ok 1 number(s): "793715188"

Test #8:

score: 10
Accepted
time: 125ms
memory: 9640kb

input:

1000
65124 24881
375719420 -94
4 999302434
-115744070 -106840680
-4491 -69694
80130510 115744070
884143403 884143305
823311389 70451862
66629531 -411971026
69217847 -628041012
-133550850 -71227120
133550850 35613560
130213420 -634837794
36981 -59230
-106840680 -97937290
832449893 -94
-68805 -11482
-...

output:

793926172

result:

ok 1 number(s): "793926172"

Test #9:

score: 10
Accepted
time: 142ms
memory: 9812kb

input:

1000
694741260 602109092
55241 72519
36 -302219951
694741260 -602109092
-125102783 -242294495
-46316084 555793008
-694741260 -92632168
231580420 92632168
370528672 -370528672
-350211968 -350212085
-185264336 92632168
-324212588 648425176
46316084 -694741260
0 -648425176
90081 14419
19297 89067
-3527...

output:

830635936

result:

ok 1 number(s): "830635936"

Test #10:

score: 10
Accepted
time: 126ms
memory: 9740kb

input:

1000
8110708 -81107080
0 -16221416
143629 -188853
-56774956 -32442832
-223901969 223901972
291022037 -93
-32442832 64885664
-539776038 -987778256
566594615 566594426
181996 -152226
-985261063 -583106808
72996372 -40553540
48664248 -105439204
104101 -213201
-195437 -134253
-16221416 -113549912
74651 ...

output:

825411016

result:

ok 1 number(s): "825411016"