QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#344910 | #3814. Saint John Festival | KhNURE_KIVI# | AC ✓ | 14ms | 4064kb | C++20 | 3.8kb | 2024-03-05 18:34:07 | 2024-03-05 18:34:08 |
Judging History
answer
//#pragma GCC optimize("Ofast", "unroll-loops")
//#pragma GCC target("sse", "sse2", "sse3", "ssse3", "sse4")
#include <bits/stdc++.h>
#define all(a) a.begin(),a.end()
#define len(a) (int)(a.size())
#define mp make_pair
#define pb push_back
#define fir first
#define sec second
#define fi first
#define se second
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;
template<typename T>
bool umin(T &a, T b) {
if (b < a) {
a = b;
return true;
}
return false;
}
template<typename T>
bool umax(T &a, T b) {
if (a < b) {
a = b;
return true;
}
return false;
}
#ifdef KIVI
#define DEBUG for (bool _FLAG = true; _FLAG; _FLAG = false)
#define LOG(...) print(#__VA_ARGS__" ::", __VA_ARGS__) << endl
template <class ...Ts> auto &print(Ts ...ts) { return ((cerr << ts << " "), ...); }
#else
#define DEBUG while (false)
#define LOG(...)
#endif
const int max_n = -1, inf = 1000111222;
struct Point
{
int x,y;
};
ostream& operator<<(ostream& os,const Point& a)
{
return os<<"{"<<a.x<<","<<a.y<<"}";
}
const bool operator<(const Point& lhs,const Point& rhs)
{
return mp(lhs.x,lhs.y)<mp(rhs.x,rhs.y);
}
Point operator-(const Point& lhs,const Point& rhs)
{
return Point{lhs.x-rhs.x,lhs.y-rhs.y};
}
ll calc(const Point& a,const Point& b)
{
return 1ll * a.x * b.y - 1ll * a.y * b.x;
}
bool cw(const Point& a,const Point& b)
{
return 1ll * a.x * b.y - 1ll * a.y * b.x < 0;
}
bool ccw(const Point& a,const Point& b)
{
return 0 < 1ll * a.x * b.y - 1ll * a.y * b.x;
}
bool cw(const Point& a,const Point& b,const Point& c)
{
return cw(b-a, c-a);
}
bool ccw(const Point& a,const Point& b,const Point& c)
{
return ccw(b-a, c-a);
}
vector<Point> convex_hull(vector<Point> v)
{
sort(all(v));
if (len(v)<=2){
return v;
}
vector<Point> up,down;
for (auto p:v){
if (!ccw(v[0],p,v.back())){
while (len(up)>=2 && !cw(up[len(up)-2],up.back(),p)){
up.pop_back();
}
up.pb(p);
}
}
for (auto p:v){
if (!cw(v[0],p,v.back())){
while (len(down)>=2 && !ccw(down[len(down)-2],down.back(),p)){
down.pop_back();
}
down.pb(p);
}
}
down.pop_back();
reverse(all(down));
down.pop_back();
up.insert(up.end(), all(down));
return up;
}
inline ll area (Point a, Point b, Point c) {
return abs(calc(b - a, c - a));
}
inline bool inside(Point a, Point b, Point c, Point p) {
return area(a, b, c) == area(a, b, p) + area(a, c, p) + area(b, c, p);
}
int main() {
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
ios_base::sync_with_stdio(0);
cin.tie(0);
int n;
cin>>n;
vector<Point> v;
for (int i=0;i<n;i++){
int x,y;
cin>>x>>y;
v.pb(Point{x,y});
}
auto H=convex_hull(v);
// DEBUG{
// cerr<<"up :: ";
// for (auto i:up){
// cerr<<i<<" ";
// }
// cerr<<"\n";
// cerr<<"down :: ";
// for (auto i:down){
// cerr<<i<<" ";
// }
// cerr<<"\n";
// };
int ans=0;
int q;
cin>>q;
LOG(q);
while (q--){
int x,y;
cin>>x>>y;
int l = 1, r = len(H) - 2;
Point P{x, y};
while (l < r) {
int mid = (l + r + 1) >> 1;
if (!ccw(H[mid] - H[0], P - H[0])) {
l = mid;
}
else {
r = mid - 1;
}
}
if (inside(H[0], H[r], H[r + 1], P)) {
++ans;
}
}
cout<<ans<<"\n";
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3532kb
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: 1ms
memory: 3564kb
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: 0ms
memory: 3548kb
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: 3820kb
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: 0ms
memory: 3544kb
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: 3824kb
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: 0ms
memory: 3492kb
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: 3536kb
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: 0ms
memory: 3592kb
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: 0ms
memory: 3544kb
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: 3600kb
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: 9ms
memory: 3740kb
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: 2ms
memory: 4064kb
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: 3808kb
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: 3700kb
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: 2ms
memory: 4048kb
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: 14ms
memory: 3744kb
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: 13ms
memory: 3680kb
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: 3764kb
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: 10ms
memory: 3696kb
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: 10ms
memory: 3764kb
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: 10ms
memory: 3788kb
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: 7ms
memory: 3728kb
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: 6ms
memory: 3704kb
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: 3796kb
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: 0ms
memory: 3616kb
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: 0ms
memory: 3828kb
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: 0ms
memory: 3576kb
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: 3548kb
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: 0ms
memory: 3636kb
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: 0ms
memory: 3840kb
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'