QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#67522 | #2676. 鱼 | alpha1022 | 100 ✓ | 420ms | 10368kb | C++20 | 3.4kb | 2022-12-10 16:55:54 | 2022-12-10 16:55:57 |
Judging History
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"