QOJ.ac
QOJ
The 2nd Universal Cup Finals is coming! Check out our event page, schedule, and competition rules!
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#122315 | #523. 部落战争 | lunchbox# | 100 ✓ | 105ms | 13212kb | C++17 | 2.5kb | 2023-07-10 02:37:31 | 2024-07-04 00:35:37 |
Judging History
answer
#include "bits/stdc++.h"
using namespace std;
#define FOR(i,a,b) for (int i = (a) ; i < (b); i++)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); i--)
#define R0F(i,a) ROF(i,0,a)
#define ar array
#define all(v) begin(v),end(v)
#define sz(v) static_cast<int>(v.size())
typedef vector<int> vi;
typedef long long ll;
struct Point {
ll x,y;
bool operator==(const Point& p) const { return (x == p.x && y == p.y); }
Point operator-(const Point &p) const { return {x-p.x,y-p.y}; }
Point operator+(const Point &p) const { return {x+p.x,y+p.y}; }
friend ll abs(const Point& a) { return a.x*a.x+a.y*a.y; }
friend ll cross(const Point &a, const Point &b) { return a.x*b.y-a.y*b.x; }
friend ll cross(const Point& p, const Point& a, const Point& b) { return cross(a-p,b-p); }
};
bool hCmp(const Point& p, const Point& q) {
return p.y < q.y || (p.y == q.y && p.x < q.x);
}
bool angleCmp(const Point& p, const Point& q) {
return cross(p,q) > 0 || (cross(p,q) == 0 && abs(p) < abs(q));
}
vector<Point> graham(vector<Point> p) {
sort(all(p),hCmp);
Point base = p[0];
for (Point &a : p) a = a-base;
sort(1+all(p),angleCmp);
vector<Point> h;
for (Point a : p) {
while (sz(h) > 1 && cross(h[sz(h)-2],h[sz(h)-1],a) <= 0) h.pop_back();
h.push_back(a);
}
for (Point &a : h) a = a+base;
return h;
}
vector<Point> minkowski(vector<Point> p, vector<Point> q) {
vector<Point> sp(sz(p)), sq(sz(q));
F0R(i,sz(p)) sp[i] = p[(i+1)%sz(p)]-p[i];
F0R(i,sz(q)) sq[i] = q[(i+1)%sz(q)]-q[i];
vector<Point> h = {p[0]+q[0]};
int i = 0, j = 0;
while (i < sz(p) && j < sz(q)) h.push_back(h.back()+(cross(sp[i],sq[j]) >= 0 ? sp[i++] : sq[j++]));
while (i < sz(p)) h.push_back(h.back()+sp[i++]);
while (j < sz(q)) h.push_back(h.back()+sq[j++]);
return h;
}
bool inside(vector<Point> &h, Point p) {
if (cross(p,h[0]) > 0 || cross(h.back(),p) > 0) return 0;
int i = lower_bound(all(h),p,angleCmp)-begin(h)-1;
return cross(h[i],p,h[(i+1)%sz(h)]) <= 0;
}
int32_t main() {
ios::sync_with_stdio(false); cin.tie(NULL);
cin.exceptions(cin.failbit);
int n, m, q;
cin >> n >> m >> q;
vector<Point> tp(n), tq(m);
for (Point &a : tp) cin >> a.x >> a.y;
for (Point &a : tq) cin >> a.x >> a.y, a.x *= -1, a.y *= -1;
auto h = graham(minkowski(graham(tp),graham(tq)));
Point base = h[0];
for (Point &a : h) a = a-base;
while (q--) {
Point p;
cin >> p.x >> p.y;
p = p-base;
cout << inside(h,p) << '\n';
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 10
Accepted
time: 1ms
memory: 3548kb
input:
5 5 500 6407435 3293303 7667584 -28726709 12981947 3232993 -4728920 -20310419 11417244 -21375059 -9897535 1003568 11250465 -455741 -212338 27421583 -8617310 23838234 1170809 22010017 9475604 -55467994 -4050339 3741774 -837777 3712301 21965125 2292518 15461481 -52915993 6607803 -55284619 4978498 3464...
output:
1 0 1 1 1 1 0 1 0 1 1 0 1 0 0 0 1 1 1 1 1 0 1 0 1 0 0 0 1 1 1 0 0 0 0 1 0 1 1 1 1 0 1 1 1 1 1 0 0 1 1 1 0 0 1 0 1 0 0 0 1 0 1 0 0 1 0 0 1 1 1 0 0 0 0 1 0 0 0 1 1 0 1 1 1 1 0 0 1 0 1 1 0 1 1 0 1 0 0 0 0 0 0 1 1 1 1 0 1 1 1 0 1 1 0 1 0 0 1 0 0 1 1 0 1 1 1 1 1 1 0 1 0 0 1 0 1 0 0 1 0 0 1 1 1 1 0 1 0 1 ...
result:
ok 500 lines
Test #2:
score: 10
Accepted
time: 0ms
memory: 3616kb
input:
5 5 500 -27523822 3903432 -8164905 12245974 -12788492 -18439238 -9257256 12571383 -7088899 -13518632 8395941 908038 3503624 10427724 -14313118 13946163 -8810192 15122696 -23606580 1742581 -2846782 -33320015 10422149 -23265478 -28254784 -10728385 -25177201 8093012 -7071570 -16767903 -24720747 8309611...
output:
0 0 0 1 1 1 1 0 1 1 1 1 1 1 0 0 1 1 0 1 1 1 1 0 0 1 1 1 1 1 1 1 1 0 0 0 1 0 0 1 0 1 0 0 0 0 1 1 0 0 1 0 1 1 0 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 0 1 1 0 1 0 1 0 0 1 1 1 1 1 1 1 0 0 1 1 0 0 0 1 1 1 0 1 0 1 1 0 1 0 1 0 0 1 1 1 1 0 0 0 0 1 0 0 0 1 1 1 1 1 0 1 0 1 0 1 1 0 0 1 0 1 0 1 0 1 1 0 0 0 1 ...
result:
ok 500 lines
Test #3:
score: 10
Accepted
time: 1ms
memory: 3844kb
input:
50 50 500 4254966 4514473 -10243311 29338943 -11714256 28967870 -3638225 -329846 -11636788 -126679 -5182905 -625577 6032976 21796923 -13140961 28452003 1041973 27162958 -2756343 -84802 -7820141 29623403 -1439665 28473013 -2457947 28853419 -7990305 29616231 -7601697 29629812 -14884269 1278440 -998615...
output:
1 0 0 1 1 1 0 1 1 1 1 0 1 1 0 0 1 1 1 1 1 1 1 1 1 1 0 1 0 0 1 1 0 0 1 0 0 1 1 1 0 1 0 1 1 0 0 1 0 1 1 0 0 0 0 0 0 1 0 1 1 1 1 1 0 1 1 1 0 1 0 1 0 1 1 1 1 1 0 1 1 0 0 0 1 0 0 0 0 0 0 1 0 1 0 1 1 0 0 1 0 1 1 1 0 1 0 1 1 0 0 1 1 0 1 1 0 1 0 1 1 0 1 1 0 0 1 1 0 1 0 0 0 1 1 0 0 0 1 1 0 0 0 0 1 1 0 0 0 1 ...
result:
ok 500 lines
Test #4:
score: 10
Accepted
time: 1ms
memory: 3604kb
input:
50 50 500 9401701 -3609043 2012208 -1102882 -1811540 -26010495 -5041437 -3110073 10286335 -4329717 12578870 -20602424 10667571 -4684127 12022858 -6227670 6703376 -2076756 -3916528 -2467881 -8883942 -6948248 4710266 -26206538 8123463 -24867007 5052685 -26121576 -4028108 -2524942 -1941055 -1669813 319...
output:
1 0 1 0 0 1 1 0 1 0 1 0 1 0 0 1 0 1 1 0 1 1 0 0 0 1 1 1 1 1 1 0 1 0 0 1 1 0 1 1 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 1 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 1 0 0 1 0 1 0 1 1 1 1 0 1 0 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 0 0 1 1 0 1 0 1 0 0 0 0 1 0 0 0 1 0 0 1 0 1 1 1 1 1 0 1 0 1 0 0 0 1 0 0 1 0 0 1 0 0 1 1 0 0 1 ...
result:
ok 500 lines
Test #5:
score: 10
Accepted
time: 9ms
memory: 4996kb
input:
10000 10000 500 1666056 -27430003 -4367330 9570472 18716225 -12240967 -1787485 -27373792 -15436704 1726451 5020083 -26867542 -2574044 -27271537 -11443050 6074066 -4820607 -26789265 15100955 2873536 -9623440 7349040 976214 10130141 -9144842 7634171 6079703 9216512 15077673 -20242861 16905511 69303 13...
output:
0 0 0 0 1 0 0 1 1 0 1 0 0 0 0 0 1 0 0 1 0 1 0 1 0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 1 0 0 1 0 1 0 0 1 1 0 1 1 0 0 1 0 0 1 1 1 0 0 1 0 1 0 0 1 1 0 0 0 0 1 1 1 1 0 0 1 1 1 1 1 1 0 0 0 1 1 1 1 0 0 0 1 0 0 0 1 0 1 0 1 0 1 0 1 1 1 0 1 1 0 1 0 0 1 1 0 0 1 1 0 0 0 0 0 0 1 1 1 0 1 1 1 0 1 1 1 0 1 0 1 1 0 0 0 0 1 ...
result:
ok 500 lines
Test #6:
score: 10
Accepted
time: 9ms
memory: 4884kb
input:
10000 10000 500 9282217 -4781364 1501964 25031109 -3834648 -5391055 8360673 -5218666 -7317209 -3446949 -10874263 199999 -3638519 23977553 -10806642 104184 9180387 23342430 8585209 23627902 -742433 24790641 2593801 -6522640 -13108369 4871264 -3278720 24111737 -1204794 24700179 2670075 25028975 145219...
output:
0 0 0 0 0 1 0 1 0 0 1 1 1 1 1 1 0 0 1 1 1 1 1 0 0 0 1 1 0 1 1 1 0 1 1 1 1 0 1 1 0 0 0 0 0 1 0 0 1 0 1 1 1 1 1 1 0 1 1 1 1 1 0 0 1 0 1 1 1 1 0 0 0 0 0 1 1 1 0 0 0 0 0 1 1 0 1 0 0 1 0 0 1 0 1 0 1 1 1 0 1 0 1 1 1 0 1 0 0 0 0 1 1 0 1 0 1 0 1 1 1 1 1 1 0 1 0 1 1 1 1 0 1 1 1 0 1 1 1 1 0 0 1 0 1 1 1 0 0 1 ...
result:
ok 500 lines
Test #7:
score: 10
Accepted
time: 9ms
memory: 4868kb
input:
10000 10000 500 18739956 22581499 226899 20847190 4459986 -8474225 19625260 22085584 17107612 -8505721 1592846 21819795 4911498 -8647734 754040 -6425195 11298530 -9694797 8002434 -9467273 15632721 -9011669 19047199 -7595729 26034505 15249508 1304680 21631076 16199900 -8834823 20427260 -6752268 -5838...
output:
0 0 1 1 1 1 1 0 1 0 0 1 1 1 1 1 1 0 0 1 0 1 1 1 1 0 0 0 1 1 1 1 0 1 0 1 0 1 0 0 1 0 1 1 1 0 0 0 0 0 0 1 0 1 1 0 1 1 0 1 1 1 1 0 1 1 0 0 1 0 1 0 0 0 0 1 1 0 0 1 1 0 1 1 1 0 0 0 0 0 1 0 0 0 0 1 1 1 1 0 0 0 1 1 1 0 1 1 1 1 1 0 0 0 1 0 1 1 0 0 0 0 1 1 1 0 1 1 0 0 1 0 1 0 1 1 0 0 1 0 1 1 0 1 1 0 0 0 1 0 ...
result:
ok 500 lines
Test #8:
score: 10
Accepted
time: 100ms
memory: 13212kb
input:
100000 100000 100000 24235601 -13951926 -10355885 -24094242 -5635989 -27027698 12252374 12885344 6137155 -28841530 15967851 10799403 9725989 13814468 -7061607 12038424 -9834599 -24505790 11646839 -27414386 -2187954 -28266157 -18126630 -3597220 3069276 14729493 -199316 14425458 11896146 -27311875 -12...
output:
0 0 1 0 0 1 0 1 0 0 0 1 1 1 1 1 1 0 1 1 0 1 0 0 1 0 0 1 1 0 1 1 1 1 1 1 1 0 1 1 1 0 0 0 1 0 1 0 0 1 1 0 0 1 0 0 1 1 1 1 0 0 1 1 0 1 1 1 1 1 0 0 1 0 1 1 1 1 1 0 1 1 0 1 0 1 0 0 0 0 0 1 0 0 1 1 1 0 0 1 1 0 1 1 0 1 1 0 0 0 0 1 0 1 1 1 0 1 1 0 0 1 1 0 1 1 0 1 1 1 1 1 0 0 1 0 0 1 1 0 1 0 0 1 1 0 0 0 0 0 ...
result:
ok 100000 lines
Test #9:
score: 10
Accepted
time: 98ms
memory: 12876kb
input:
100000 100000 100000 8354421 -26671439 8956353 6194768 18000019 5113843 -731040 989961 20842988 3589967 1941343 -23926046 17724523 5225919 26327648 -18097349 26513711 -2848520 19914037 -24750782 19992615 -24705163 -3889910 -4001319 26006870 -1907798 11797680 6399489 3081377 -24663720 14262223 -26766...
output:
0 0 1 1 1 0 0 0 1 0 1 0 0 0 0 1 0 1 1 1 0 1 0 1 0 0 1 0 0 0 1 1 1 1 1 0 1 0 1 0 1 1 0 1 1 1 1 0 0 1 0 1 1 0 0 0 1 1 1 0 1 0 0 1 0 0 1 0 1 1 0 0 0 1 0 1 1 0 1 1 1 0 0 0 0 1 1 1 1 1 1 1 0 0 1 0 0 0 1 0 1 1 1 0 0 1 1 1 0 1 0 0 1 1 1 1 0 0 1 0 0 1 1 0 0 0 0 1 0 1 0 0 1 1 1 1 1 1 1 1 1 0 1 0 1 1 1 0 1 0 ...
result:
ok 100000 lines
Test #10:
score: 10
Accepted
time: 105ms
memory: 12944kb
input:
100000 100000 100000 -17714771 -18844934 13960381 -21362034 -13107507 -24716099 -5216508 -28653304 -6830004 7079906 -7371497 6895381 15737377 -2830941 -16200790 -21359312 -17628244 -19016144 8224158 -26586063 -732489 7976996 13458776 -22030283 -5650557 -28549478 16498589 -4770663 4862335 -28120485 8...
output:
1 0 0 1 1 1 1 1 1 0 0 1 0 1 1 1 0 0 1 0 0 1 1 1 0 0 0 0 0 1 0 1 1 1 0 1 1 0 1 0 1 0 1 0 1 0 1 1 1 1 1 1 1 0 0 1 0 1 0 0 1 1 0 0 1 1 0 1 1 1 1 0 0 1 1 1 1 1 1 1 0 1 0 0 1 0 1 1 1 0 0 0 1 1 0 1 0 1 0 0 0 1 1 1 1 0 1 1 0 1 0 1 0 1 0 0 0 0 0 0 1 1 1 0 0 0 1 1 0 0 1 0 0 0 1 1 0 1 1 0 0 1 0 1 0 1 0 1 1 0 ...
result:
ok 100000 lines
Extra Test:
score: 0
Extra Test Passed