QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#557060 | #6403. Master of Polygon | pandapythoner | TL | 1847ms | 10468kb | C++23 | 2.3kb | 2024-09-11 01:49:50 | 2024-09-11 01:49:51 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define len(a) int((a).size())
#define all(a) begin(a), end(a)
#define rep(i, n) for (int i = 0; i < (n); i++)
mt19937 rnd(234234);
ld pi = atan2l(0, -1);
struct vec {
ll x, y;
vec() {}
vec(ll x, ll y) : x(x), y(y) {}
};
vec operator+(const vec& a, const vec& b) {
return vec{ a.x + b.x, a.y + b.y };
}
vec operator-(const vec& a, const vec& b) {
return vec{ a.x - b.x, a.y - b.y };
}
ll operator*(const vec& a, const vec& b) {
return a.x * b.x + a.y * b.y;
}
ll operator%(const vec& a, const vec& b) {
return a.x * b.y - a.y * b.x;
}
ll sign(ll x) {
if (x > 0) return 1;
if (x < 0) return -1;
return 0;
}
bool intersects(const vec& a, const vec& b, const vec& c, const vec& d) {
if ((a - b) % (c - d) == 0) {
if ((c - a) % (d - a) != 0) return false;
if (max(a.x, b.x) < min(c.x, d.x) or max(c.x, d.x) < min(a.x, b.x)) return false;
if (max(a.y, b.y) < min(c.y, d.y) or max(c.y, d.y) < min(a.y, b.y)) return false;
return true;
}
if (sign((b - a) % (c - a)) * sign((b - a) % (d - a)) > 0) return false;
if (sign((d - c) % (a - c)) * sign((d - c) % (b - c)) > 0) return false;
return true;
}
int n, q;
vector<vec> poly;
vector<pair<vec, vec>> tests;
vector<int> result;
void solve_slow() {
result.resize(q);
rep(i, q) {
auto& [a, b] = tests[i];
result[i] = false;
rep(j, n) {
auto& c = poly[j];
auto& d = poly[j == n - 1 ? 0 : j + 1];
if (intersects(a, b, c, d)) {
result[i] = true;
break;
}
}
}
}
signed main() {
cin.tie(nullptr)->sync_with_stdio(false);
cin >> n >> q;
poly.resize(n);
rep(i, n) cin >> poly[i].x >> poly[i].y;
tests.resize(q);
rep(i, q) {
cin >> tests[i].first.x >> tests[i].first.y >> tests[i].second.x >> tests[i].second.y;
}
solve_slow();
rep(i, q) {
if (result[i]) {
cout << "YES" << "\n";
} else {
cout << "NO" << "\n";
}
}
return 0;
}
/*
4 6
1 1
4 1
4 4
1 4
0 2 2 0
0 1 1 1
0 0 5 5
2 2 4 2
2 2 3 2
5 1 0 2
*/
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3536kb
input:
4 6 1 1 4 1 4 4 1 4 0 2 2 0 0 1 1 1 0 0 5 5 2 2 4 2 2 2 3 2 5 1 0 2
output:
YES YES YES YES NO YES
result:
ok 6 token(s): yes count is 5, no count is 1
Test #2:
score: 0
Accepted
time: 54ms
memory: 10024kb
input:
20 200000 8838 9219 12190 11292 15953 7581 16690 6159 21104 5484 8978 1076 4354 1065 1261 676 12684 14159 15469 22416 13493 28027 15531 26837 18253 26053 26444 24253 22160 19958 24879 12856 28793 22156 25300 10245 14749 15078 12946 13942 26544 28338 18806 21279 5592 29200 20935 25253 28189 17513 215...
output:
YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES NO YES NO YES YES NO YES NO YES YES YES NO YES YES YES NO YES YES YES NO YES YES YES YES YES YES YES YES YES NO NO YES YES YES YES NO NO YES YES YES YES YES YES YES YES YES YES NO YES NO YES YES YES YES YES YES YES NO NO YES YES YES YES...
result:
ok 200000 token(s): yes count is 156067, no count is 43933
Test #3:
score: 0
Accepted
time: 183ms
memory: 10032kb
input:
500 200000 17729 7936 17684 8099 17925 10195 17441 9150 17314 9604 17008 8764 17003 7525 16501 4085 16247 5851 16768 625 16492 706 15995 4316 16287 976 16032 629 15217 133 15692 4260 16153 6940 15550 5717 15493 4823 15085 4477 14465 4830 13595 4960 13721 3490 13309 2776 11167 3053 14319 2156 14626 2...
output:
YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES NO YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES Y...
result:
ok 200000 token(s): yes count is 197031, no count is 2969
Test #4:
score: 0
Accepted
time: 403ms
memory: 10296kb
input:
2000 200000 15746 1958 15965 1785 16322 2203 16779 3060 15774 2055 15869 2486 16141 3025 14987 1567 16314 3508 14816 1823 13841 1058 15595 3183 15716 4094 15939 4023 16426 4179 16507 5225 17035 6211 17233 5343 18059 5915 17140 5103 17154 4324 17471 4562 18065 5767 20733 10646 21651 12444 18707 6969 ...
output:
YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES ...
result:
ok 200000 token(s): yes count is 199151, no count is 849
Test #5:
score: 0
Accepted
time: 1847ms
memory: 10352kb
input:
2000 200000 11439 4221 11601 4531 11351 4595 10165 4725 11049 4209 9643 4623 8884 4596 8598 4376 10987 3767 10577 3606 10678 3417 10159 3481 10288 3302 11157 2781 10513 2652 10601 2489 10785 2201 9881 2932 10877 1775 9578 3034 9083 3337 8118 4188 8911 3253 10649 1785 6624 3607 6002 3749 10788 1539 8...
output:
NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO ...
result:
ok 200000 token(s): yes count is 1564, no count is 198436
Test #6:
score: 0
Accepted
time: 1820ms
memory: 10324kb
input:
2000 200000 25931 29637 25732 29388 25090 29397 24676 29660 24268 29454 24712 28969 24252 27672 23976 28067 24211 27138 24428 27732 24389 27010 24062 26426 24278 25689 24727 26596 25281 28154 25062 26750 24927 26324 24625 25457 25456 26307 25444 25561 26008 27471 26065 27717 26065 27194 25255 24568 ...
output:
NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO ...
result:
ok 200000 token(s): yes count is 5859, no count is 194141
Test #7:
score: 0
Accepted
time: 1614ms
memory: 10468kb
input:
2000 200000 14066 4014 14235 4742 15201 5329 15389 5460 11381 3722 12856 4511 8264 2372 13039 4278 11684 3711 12888 4180 11849 3607 11431 3373 9979 2823 9099 2534 9055 2434 9393 2382 9867 2512 10315 2558 8175 1662 6480 184 5437 92 4413 100 5548 790 4362 471 4463 552 4817 748 6715 1673 5807 1562 7942...
output:
NO YES YES NO YES NO NO YES NO YES NO NO NO YES NO NO NO YES NO YES YES YES YES NO YES YES NO NO NO NO YES NO NO YES NO NO YES NO YES YES NO NO YES NO YES NO NO NO NO NO NO NO NO NO NO NO NO YES NO NO YES NO NO NO NO NO NO NO NO NO YES NO NO NO YES NO NO NO NO YES NO NO YES NO NO YES NO NO NO NO NO ...
result:
ok 200000 token(s): yes count is 55692, no count is 144308
Test #8:
score: 0
Accepted
time: 1008ms
memory: 10396kb
input:
2000 200000 14977 2004 14689 1703 15835 1810 16896 1690 16802 1617 16193 869 15027 1025 14890 398 15977 29 17024 621 16998 991 17114 745 18865 277 18293 764 18306 941 19319 12 17810 1554 19311 271 17748 1881 15553 3843 17271 2971 18157 1924 19839 300 19482 727 19186 1301 19603 836 19522 1061 19765 1...
output:
YES YES YES YES YES YES YES NO YES YES YES YES YES YES YES YES YES YES YES YES YES NO YES YES YES YES YES NO NO YES YES YES YES YES NO YES YES NO YES YES YES YES YES NO YES YES YES YES NO YES NO YES YES YES YES YES YES YES YES YES YES YES YES NO YES YES YES YES YES YES NO YES NO YES YES YES YES YES ...
result:
ok 200000 token(s): yes count is 171136, no count is 28864
Test #9:
score: 0
Accepted
time: 86ms
memory: 4656kb
input:
99966 1000 25033 23639 25334 23745 25777 23856 25534 23761 24893 23589 24648 23517 24596 23501 24535 23479 24356 23416 24269 23406 24131 23319 24905 23572 24978 23588 24418 23387 23595 23085 24070 23293 23843 23200 23484 23078 23596 23125 23438 23066 23142 22915 24265 23317 23323 22980 23624 23088 2...
output:
YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES ...
result:
ok 1000 token(s): yes count is 1000, no count is 0
Test #10:
score: 0
Accepted
time: 398ms
memory: 4612kb
input:
99969 1000 19235 2200 19307 2137 19620 1920 19590 1908 19486 1919 19280 2087 19260 2029 19226 2197 19147 2281 19135 2254 19095 2304 19207 2101 18981 2354 18936 2288 18943 2166 18851 2224 18697 2428 19149 2332 18976 2371 18948 2403 19134 2347 19220 2323 19196 2374 19128 2467 19084 2485 19018 2464 190...
output:
NO NO NO YES NO NO YES NO YES NO NO NO NO YES NO NO NO NO NO NO NO YES NO YES NO NO NO NO NO NO NO YES NO NO NO NO NO NO NO NO YES YES NO NO NO YES NO NO YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES NO NO NO YES NO NO NO NO YES NO YES NO NO NO NO NO NO NO NO YES NO NO NO NO YES NO NO NO N...
result:
ok 1000 token(s): yes count is 173, no count is 827
Test #11:
score: 0
Accepted
time: 293ms
memory: 4592kb
input:
99976 1000 23538 24587 23600 24898 23569 24997 23628 25053 23693 25259 23691 25126 23674 25068 23623 24923 23664 25002 23713 25142 23659 24925 23558 24571 23523 24358 23569 24559 23578 24562 23637 24783 23621 24703 23685 24932 23735 25098 23768 25199 23802 25254 23768 25186 23774 25165 23645 24685 2...
output:
YES YES YES NO YES NO YES YES NO YES YES YES YES YES NO NO YES NO YES NO YES YES YES YES NO NO NO NO YES NO YES YES YES YES YES YES YES YES NO NO YES YES YES NO YES NO YES NO YES NO YES NO YES YES YES YES YES NO YES YES NO YES NO NO YES YES YES NO YES NO YES YES NO NO YES NO NO NO YES YES YES NO YES...
result:
ok 1000 token(s): yes count is 666, no count is 334
Test #12:
score: 0
Accepted
time: 166ms
memory: 6180kb
input:
199886 1000 14938 9857 14804 10006 14968 9807 14708 10115 14761 10098 14678 10167 14648 10192 14715 10150 14497 10337 14635 10227 14596 10269 14648 10256 14774 10175 14682 10266 14490 10424 14602 10339 14754 10214 14490 10489 14360 10622 14157 10755 14299 10632 14431 10511 14245 10670 14429 10473 14...
output:
YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES ...
result:
ok 1000 token(s): yes count is 1000, no count is 0
Test #13:
score: 0
Accepted
time: 827ms
memory: 6208kb
input:
199901 1000 1983 26999 2038 26992 2067 26988 2231 26970 2022 26966 2763 26923 2133 26996 2353 26976 2258 26995 2211 27022 2129 27045 2138 27046 2532 27004 2630 26988 3195 26898 3060 26912 3210 26895 3069 26904 2936 26918 2839 26924 2998 26888 2696 26891 2461 26909 2257 26930 1640 26991 1708 26971 18...
output:
NO NO NO NO NO NO NO NO NO NO NO NO YES NO NO YES NO NO NO NO NO NO NO NO NO NO NO YES NO NO NO NO NO NO YES YES NO NO YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO N...
result:
ok 1000 token(s): yes count is 88, no count is 912
Test #14:
score: 0
Accepted
time: 762ms
memory: 6196kb
input:
199898 1000 18799 13687 18845 13550 18777 13722 18754 13747 18726 13809 18674 13927 18698 13858 18740 13747 18818 13555 18664 13906 18651 13907 18649 13898 18605 13894 18656 13746 18693 13650 18784 13527 18811 13447 18775 13570 18818 13471 18851 13382 18907 13296 18924 13316 18943 13240 18829 13393 ...
output:
NO YES NO NO NO YES NO YES YES NO YES NO NO YES YES YES NO YES NO NO YES NO NO YES NO NO NO NO NO NO YES NO NO YES NO NO NO NO YES NO YES NO NO YES NO NO NO NO NO NO YES NO NO NO NO NO NO NO NO NO NO NO NO YES NO NO NO YES NO YES NO NO NO NO NO YES NO NO YES NO NO YES NO NO NO NO NO NO YES NO NO NO ...
result:
ok 1000 token(s): yes count is 235, no count is 765
Test #15:
score: 0
Accepted
time: 545ms
memory: 6272kb
input:
199886 1000 10118 8021 10120 8003 10112 8046 10126 8048 10157 8041 10255 8007 10140 8106 10114 8118 10137 8118 10284 8037 10259 8097 10381 8066 10302 8091 10209 8127 10185 8149 10199 8146 10314 8117 10340 8108 10261 8229 10328 8182 10333 8267 10377 8257 10465 8176 10416 8235 10421 8256 10400 8332 10...
output:
NO YES YES YES NO YES YES YES YES YES YES YES YES YES NO YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES NO YES YES YES YES YES YES YES YES NO NO YES YES YES YES YES YES YES NO YES YES YES YES NO YES YES YES YES NO NO YES YES YES YES YES NO YES YES YES YES YES YES YES YES...
result:
ok 1000 token(s): yes count is 762, no count is 238
Test #16:
score: 0
Accepted
time: 437ms
memory: 6240kb
input:
199879 1000 18589 2979 18584 2916 18708 2953 18498 2855 18498 2848 18472 2840 18436 2819 18649 2859 18521 2809 18573 2808 18386 2799 18442 2784 18486 2785 18648 2774 18360 2745 18649 2770 18730 2789 18716 2804 18731 2927 18751 2963 18855 2956 18826 2904 18833 2895 18848 2902 18851 2916 18922 2944 18...
output:
YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES ...
result:
ok 1000 token(s): yes count is 987, no count is 13
Test #17:
score: -100
Time Limit Exceeded
input:
199874 200000 8778 8537 8541 8516 8372 8496 7893 8430 7794 8429 7968 8456 7837 8443 7844 8452 8024 8493 8016 8501 8137 8518 7682 8492 7633 8489 7684 8508 7633 8520 8523 8538 8449 8539 7714 8536 7660 8547 8781 8557 7918 8557 8942 8561 9037 8578 9079 8577 9031 8586 9310 8621 9280 8625 9224 8619 8927 8...