QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#125738 | #3814. Saint John Festival | GoatGirl98 | AC ✓ | 12ms | 3076kb | C++14 | 3.9kb | 2023-07-17 15:03:04 | 2023-07-17 15:03:05 |
Judging History
answer
#include <stdio.h>
#include <vector>
#include <algorithm>
#define getchar getchar_unlocked
#define putchar putchar_unlocked
using namespace std;
typedef long long i64;
void wr(i64 x)
{
if (x < 0)
putchar('-'), x = -x;
if (x > 9)
wr(x / 10);
putchar(x % 10 + 48);
}
int rd()
{
int k = 0, f = 1;
char c = getchar();
while (c < '0' || c > '9')
{
if (c == '-')
f = -1;
c = getchar();
}
while (c >= '0' && c <= '9')
{
k = (k << 1) + (k << 3) + (c ^ '0');
c = getchar();
}
return f > 0 ? k : -k;
}
struct point
{
int x, y;
point(int _x = 0, int _y = 0) : x(_x), y(_y) {}
void input() { x = rd(), y = rd(); }
point operator-(const point& o) const { return point(x - o.x, y - o.y); }
// dot product of vector
i64 operator*(const point& o) const { return 1ll * x * o.x + 1ll * y * o.y; }
// cross product of vector
i64 operator^(const point& o) const { return 1ll * x * o.y - 1ll * y * o.x; }
i64 dis2(const point& o) const { return 1ll * (x - o.x) * (x - o.x) + 1ll * (y - o.y) * (y - o.y); }
bool operator<(const point& o) const { return (x ^ o.x) ? (x < o.x) : (y < o.y); }
bool operator==(const point& o) const { return (x == o.x) && (y == o.y); }
};
// andrew O(nlogn)
// clockwise : ((points[stk[stk.size() - 1]] - points[stk[stk.size() - 2]]) ^ (points[i] - points[stk[stk.size() - 1]])) <= 0
// anticlockwise : ((points[stk[stk.size() - 1]] - points[stk[stk.size() - 2]]) ^ (points[i] - points[stk[stk.size() - 2]])) <= 0
vector<point> get_convex(vector<point>& points)
{
int n = (int)points.size();
sort(points.begin(), points.end());
vector<int> stk;
vector<bool> used(n);
stk.push_back(0);
// upper convex
for (int i = 1; i < n; ++i)
{
while (stk.size() >= 2 && ((points[stk[stk.size() - 1]] - points[stk[stk.size() - 2]]) ^ (points[i] - points[stk[stk.size() - 2]])) <= 0)
used[stk.back()] = false, stk.pop_back();
used[i] = true, stk.push_back(i);
}
// stk.back() == n - 1
// lower convex
int upper_size = stk.size();
for (int i = n - 2; i >= 0; --i)
{
if (used[i])
continue;
while (stk.size() > upper_size && ((points[stk[stk.size() - 1]] - points[stk[stk.size() - 2]]) ^ (points[i] - points[stk[stk.size() - 2]])) <= 0)
used[stk.back()] = false, stk.pop_back();
used[i] = true, stk.push_back(i);
}
// stk.back() == stk[0]
vector<point> ret;
for (int i = 0; i < stk.size(); ++i)
ret.push_back(points[stk[i]]);
return ret;
}
bool in_convex(const vector<point>& hull, const point& p)
{
int n = hull.size() - 1;
if (n == 1)
return p == hull[0];
else if (n == 2)
return (((p - hull[0]) ^ (hull[1] - hull[0])) == 0) && (((p - hull[0]) * (p - hull[1])) <= 0);
if (((p - hull[0]) ^ (hull[1] - hull[0])) > 0)
return false;
if (((p - hull[0]) ^ (hull[n - 1] - hull[0])) < 0)
return false;
int l = 1, r = n - 2;
while (l <= r)
{
int mi = (l + r) >> 1;
i64 a_1 = (hull[mi] - hull[0]) ^ (p - hull[0]), a_2 = (hull[mi + 1] - hull[0]) ^ (p - hull[0]);
if (a_1 >= 0 && a_2 <= 0)
return ((hull[mi + 1] - hull[mi]) ^ (p - hull[mi])) >= 0;
else if (a_1 < 0)
r = mi - 1;
else
l = mi + 1;
}
return false;
}
int main()
{
int T = 1;
for (int t = 1; t <= T; ++t)
{
// printf("Case %d:\n", t);
int n = rd();
vector<point> points(n);
for (int i = 0; i < n; ++i)
points[i].input();
vector<point> hull = get_convex(points);
int q = rd(), ans = 0;
point p;
while (q--)
p.input(), ans += in_convex(hull, p);
wr(ans), putchar('\n');
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 2884kb
input:
4 1 1 4 1 4 4 1 4 32 0 0 1 0 2 0 3 0 4 0 5 0 0 1 2 1 3 1 5 1 0 2 1 2 2 2 3 2 4 2 5 2 0 3 1 3 2 3 3 3 4 3 5 3 0 4 2 4 3 4 5 4 0 5 1 5 2 5 3 5 4 5 5 5
output:
12
result:
ok single line: '12'
Test #2:
score: 0
Accepted
time: 0ms
memory: 2772kb
input:
14 4 4 5 3 5 5 6 5 7 1 7 4 7 7 8 2 8 6 8 8 9 4 9 5 9 6 9 7 29 1 8 2 2 2 4 2 6 3 1 3 4 4 2 4 3 5 1 5 4 5 7 6 1 6 2 6 3 6 4 6 6 7 2 7 3 7 5 9 1 9 2 9 3 9 8 8 7 8 5 8 4 8 3 8 1 7 6
output:
13
result:
ok single line: '13'
Test #3:
score: 0
Accepted
time: 1ms
memory: 2776kb
input:
14 8 2 7 3 1 3 2 2 7 1 6 2 3 5 4 1 6 1 5 5 4 3 4 6 5 4 5 1 29 1 1 1 2 1 4 8 9 8 1 7 5 1 5 7 2 6 8 1 7 2 8 5 3 6 3 6 4 2 6 2 3 2 4 4 7 5 2 4 8 2 1 3 1 4 5 4 4 3 4 3 6 3 2 4 2 3 3
output:
13
result:
ok single line: '13'
Test #4:
score: 0
Accepted
time: 1ms
memory: 2880kb
input:
14 1 8 2 7 6 5 4 5 4 9 4 6 5 4 5 7 5 9 2 9 3 9 3 8 8 7 7 8 29 1 1 1 9 2 5 8 9 8 8 8 6 2 8 3 7 3 6 8 5 8 3 7 2 7 7 7 6 7 4 3 2 4 7 4 8 5 8 5 6 5 5 6 8 6 9 7 9 6 7 6 6 5 3 5 2 6 4
output:
13
result:
ok single line: '13'
Test #5:
score: 0
Accepted
time: 1ms
memory: 2728kb
input:
29 1 1 1 2 1 4 8 9 8 1 7 5 1 5 7 2 6 8 1 7 2 8 5 3 6 3 6 4 2 6 2 3 2 4 4 7 5 2 4 8 2 1 3 1 4 5 4 4 3 4 3 6 3 2 4 2 3 3 14 8 2 7 3 1 3 2 2 7 1 6 2 3 5 4 1 6 1 5 5 4 3 4 6 5 4 5 1
output:
14
result:
ok single line: '14'
Test #6:
score: 0
Accepted
time: 0ms
memory: 2656kb
input:
6 8 4 7 1 8 2 6 3 4 4 11 4 17 12 4 9 2 8 1 8 3 8 5 7 2 6 4 5 3 5 2 6 1 3 5 12 5 9 7 10 1 5 5 4 7 1 2
output:
4
result:
ok single line: '4'
Test #7:
score: 0
Accepted
time: 1ms
memory: 2660kb
input:
7 8 4 7 1 9 7 8 2 6 3 4 4 11 4 16 12 4 9 2 8 1 8 3 8 5 7 2 6 4 5 3 5 2 6 1 3 5 12 5 10 1 5 5 4 7 1 2
output:
5
result:
ok single line: '5'
Test #8:
score: 0
Accepted
time: 0ms
memory: 2716kb
input:
7 8 4 7 1 9 7 8 2 6 3 4 4 9 2 11 4 15 12 4 8 1 8 3 8 5 7 2 6 4 5 3 5 2 6 1 3 5
output:
5
result:
ok single line: '5'
Test #9:
score: 0
Accepted
time: 1ms
memory: 2716kb
input:
7 8 4 7 1 9 7 5 3 8 2 6 3 9 2 11 4 15 12 4 8 1 8 3 4 4 8 5 7 2 6 4 5 2 6 1 3 5
output:
4
result:
ok single line: '4'
Test #10:
score: 0
Accepted
time: 1ms
memory: 2832kb
input:
123 0 1 1 19 18 171 153 969 816 3876 3060 11628 8568 27132 18564 50388 31824 75582 43758 92378 48620 92378 43758 75582 31824 50388 18564 27132 8568 11628 3060 3876 816 969 153 171 18 19 1 1 3249 4142 5760 7676 8960 12236 25454 39216 26754 41496 27729 43206 32724 52288 33273 53447 34776 56620 36342 5...
output:
0
result:
ok single line: '0'
Test #11:
score: 0
Accepted
time: 0ms
memory: 2768kb
input:
20 0 1 1 19 18 171 153 969 816 3876 3060 11628 8568 27132 18564 50388 31824 75582 43758 92378 48620 92378 43758 75582 31824 50388 18564 27132 8568 11628 3060 3876 816 969 153 171 18 19 1 1 103 3249 4142 5760 7676 8960 12236 25454 39216 26754 41496 27729 43206 32724 52288 33273 53447 34776 56620 3634...
output:
103
result:
ok single line: '103'
Test #12:
score: 0
Accepted
time: 3ms
memory: 2936kb
input:
10000 313312 36161 6760 418062 329745 970120 756680 70914 140064 152948 169109 125153 791089 93470 452634 2249 45995 290528 107245 190577 822568 882033 68673 752896 135086 841815 2462 450445 30525 327974 277777 52098 523553 556 999985 496231 103196 804214 999632 519159 32 494346 944068 270211 985890...
output:
39321
result:
ok single line: '39321'
Test #13:
score: 0
Accepted
time: 0ms
memory: 2876kb
input:
9999 3549469 4957057 3566255 4982345 3589124 5016797 3609683 5047769 3618384 5060877 3704239 5190217 3706164 5193117 3744125 5250305 3788400 5317005 3814888 5356909 3839990 5394725 3866555 5434745 3919762 5514901 3989678 5620229 4024328 5672429 4044502 5702821 4103407 5791561 4110029 5801537 4128355...
output:
2785
result:
ok single line: '2785'
Test #14:
score: 0
Accepted
time: 2ms
memory: 2796kb
input:
9999 0 1 1 29 28 406 378 3654 3276 23751 20475 118755 98280 475020 376740 1560780 1184040 4292145 3108105 10015005 6906900 20030010 13123110 34597290 21474180 51895935 30421755 67863915 37442160 77558760 40116600 77558760 37442160 67863915 30421755 51895935 21474180 34597290 13123110 20030010 690690...
output:
2785
result:
ok single line: '2785'
Test #15:
score: 0
Accepted
time: 2ms
memory: 2840kb
input:
9999 3549469 4957056 3566255 4982345 3589124 5016793 3609683 5047761 3618390 5060870 3704240 5190220 3706164 5193124 3744125 525035 3788400 5317051 3814888 5356910 3839990 5394726 3866555 5434746 3919762 5514902 3989678 5620229 4024328 5672420 4044502 5702830 4103407 5791562 4110029 580153 4128355 5...
output:
2848
result:
ok single line: '2848'
Test #16:
score: 0
Accepted
time: 0ms
memory: 2844kb
input:
9999 0 1 1 29 28 406 378 3654 3276 23751 20475 118755 98280 475020 376740 1560780 1184040 4292145 3108105 10015005 6906900 20030010 13123110 34597290 21474180 51895935 30421755 67863915 37442160 77558760 40116600 77558760 37442160 67863915 30421755 51895935 21474180 34597290 13123110 20030010 690690...
output:
1553
result:
ok single line: '1553'
Test #17:
score: 0
Accepted
time: 12ms
memory: 2996kb
input:
10000 23643881 378592973 533158486 223946005 174971758 520074346 38244898 406529266 454636597 461791937 336498703 528098677 518880009 365053879 298059674 1639655 361899154 16796566 97198334 475160979 202005054 528521202 511752270 155057673 138672518 33447853 498626014 130341646 189343416 11916367 10...
output:
39178
result:
ok single line: '39178'
Test #18:
score: 0
Accepted
time: 5ms
memory: 3072kb
input:
10000 995653815 434217821 56510703 730905268 964656576 315353674 539542730 1566081 438892101 3748225 80893002 227329277 901720700 202308081 663486 474250336 93469941 208910134 9093396 594924738 537663402 1420550 566716347 995528938 849532269 857529288 900783492 201047509 793129623 905061752 96336930...
output:
39406
result:
ok single line: '39406'
Test #19:
score: 0
Accepted
time: 3ms
memory: 2852kb
input:
7514 0 1 1 28 27 378 351 3276 2925 20475 17550 98280 80730 376740 296010 1184040 888030 3108105 2220075 6906900 4686825 13123110 8436285 21474180 4686825 6906900 2220075 3108105 888030 1184040 296010 376740 80730 98280 17550 20475 2925 3276 351 378 27 28 1 1 10550 12243 54810 66360 65070 78995 21643...
output:
7461
result:
ok single line: '7461'
Test #20:
score: 0
Accepted
time: 9ms
memory: 3076kb
input:
10000 166957541 19920212 171502392 518758397 136610506 34598384 481877857 105647450 453295776 73796673 361741026 16737891 322309 255285010 92693973 471345596 390452858 507536580 519897724 362373316 60744921 98370071 4598010 317906620 245189121 1008454 233620571 534603669 328473301 530070796 20675490...
output:
3
result:
ok single line: '3'
Test #21:
score: 0
Accepted
time: 3ms
memory: 2844kb
input:
10000 166957541 19920212 171502392 518758397 136610506 34598384 481877857 105647450 453295776 73796673 361741026 16737891 322309 255285010 92693973 471345596 390452858 507536580 519897724 362373316 60744921 98370071 4598010 317906620 245189121 1008454 233620571 534603669 328473301 530070796 20675490...
output:
2
result:
ok single line: '2'
Test #22:
score: 0
Accepted
time: 6ms
memory: 2964kb
input:
10000 166957541 19920212 171502392 518758397 136610506 34598384 481877857 105647450 453295776 73796673 361741026 16737891 322309 255285010 92693973 471345596 390452858 507536580 519897724 362373316 60744921 98370071 4598010 317906620 245189121 1008454 233620571 534603669 328473301 530070796 20675490...
output:
2
result:
ok single line: '2'
Test #23:
score: 0
Accepted
time: 6ms
memory: 2844kb
input:
10000 313312 36161 6760 418062 329745 970120 756680 70914 140064 152948 169109 125153 791089 93470 452634 2249 45995 290528 107245 190577 822568 882033 68673 752896 135086 841815 2462 450445 30525 327974 277777 52098 523553 556 999985 496231 103196 804214 999632 519159 32 494346 944068 270211 985890...
output:
39194
result:
ok single line: '39194'
Test #24:
score: 0
Accepted
time: 3ms
memory: 2960kb
input:
10000 166957541 19920212 171502392 518758397 136610506 34598384 481877857 105647450 453295776 73796673 361741026 16737891 322309 255285010 92693973 471345596 390452858 507536580 519897724 362373316 60744921 98370071 4598010 317906620 245189121 1008454 233620571 534603669 328473301 530070796 20675490...
output:
1
result:
ok single line: '1'
Test #25:
score: 0
Accepted
time: 2ms
memory: 2732kb
input:
5 100 50 50 150 130 190 200 50 55 145 21874 185 101 171 86 104 115 67 137 53 166 57 50 80 155 133 175 119 90 66 66 160 114 199 51 146 189 95 98 118 129 87 191 189 106 122 63 108 126 71 138 94 57 131 49 121 110 84 102 107 79 70 81 93 144 164 109 97 70 106 156 177 127 163 60 186 135 59 127 82 52 125 9...
output:
12126
result:
ok single line: '12126'
Test #26:
score: 0
Accepted
time: 2ms
memory: 2760kb
input:
6 50 150 55 145 160 180 100 50 130 190 200 50 21873 185 101 171 86 104 115 67 137 53 166 57 50 80 155 133 175 119 90 66 66 160 114 199 51 146 189 95 98 118 129 87 191 189 106 122 63 108 126 71 138 94 57 131 49 121 110 84 102 107 79 70 81 93 144 164 109 97 70 106 156 177 127 163 60 186 135 59 127 82 ...
output:
13850
result:
ok single line: '13850'
Test #27:
score: 0
Accepted
time: 1ms
memory: 2796kb
input:
5 1 2 15 2 5 10 10 1 2 1 5 5 6 11 2 10 6 16 2 12 5
output:
3
result:
ok single line: '3'
Test #28:
score: 0
Accepted
time: 1ms
memory: 2796kb
input:
4 0 0 0 5 5 5 5 0 45 1 3 6 6 3 0 3 2 2 1 6 2 1 6 5 1 2 5 0 3 4 0 1 2 3 3 1 5 4 4 6 3 5 6 3 6 2 2 3 5 4 1 1 1 6 4 5 4 2 6 4 5 0 4 6 0 1 4 2 3 2 4 4 2 1 0 6 5 5 3 0 1 4 6 3 4 6 1 3 1 0 6 2 0 4 3 5 2 0 2
output:
32
result:
ok single line: '32'
Test #29:
score: 0
Accepted
time: 1ms
memory: 2836kb
input:
6 10 5 5 15 13 19 20 5 16 18 6 14 456 7 3 16 9 19 4 17 20 20 7 18 19 21 6 8 5 9 0 10 7 0 17 14 1 12 17 15 4 13 20 3 2 4 5 16 0 19 13 17 13 20 14 18 10 21 15 8 12 9 9 10 14 8 18 11 15 9 19 14 8 12 8 15 13 13 13 2 18 0 14 3 11 1 15 4 12 2 12 5 1 3 17 16 7 19 18 17 6 7 15 18 5 21 8 10 9 11 4 9 20 14 19...
output:
143
result:
ok single line: '143'
Test #30:
score: 0
Accepted
time: 1ms
memory: 2772kb
input:
14 2 1 3 2 5 4 6 5 1 2 2 3 4 4 5 6 1 3 3 5 1 4 1 5 2 7 3 8 29 4 7 4 3 1 1 1 6 1 7 1 8 2 2 2 4 2 5 2 6 2 8 3 3 3 4 3 6 3 7 4 5 4 6 5 5 5 2 5 8 4 8 6 6 6 7 7 5 7 8 8 3 8 5 8 7 9 1
output:
13
result:
ok single line: '13'
Test #31:
score: 0
Accepted
time: 1ms
memory: 2736kb
input:
8 3 4 2 8 5 4 1 8 4 7 3 10 11 2 7 3 6 5 12 3 7 3 3 4 5 0 4 2 6
output:
3
result:
ok single line: '3'