QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#407578 | #2297. Flatland Olympics | Andycipation | AC ✓ | 39ms | 7884kb | C++20 | 3.8kb | 2024-05-09 00:21:17 | 2024-05-09 00:21:18 |
Judging History
answer
/*
* author: ADMathNoob
* created: 05/08/24 11:56:45
* problem: https://qoj.ac/problem/2297
*/
/*
Comments about problem:
*/
#include <bits/stdc++.h>
using namespace std;
#ifdef _DEBUG
#include "debug.h"
#else
#define debug(...) 42
#endif
template <class T>
int sgn(T x) {
return (x > 0) - (x < 0);
}
template <class T>
struct Point {
typedef Point P;
T x, y;
explicit Point(T x_ = 0, T y_ = 0) : x(x_), y(y_) {}
bool operator<(P p) const { return tie(x, y) < tie(p.x, p.y); }
bool operator==(P p) const { return tie(x, y) == tie(p.x, p.y); }
P operator+(P p) const { return P(x + p.x, y + p.y); }
P operator-(P p) const { return P(x - p.x, y - p.y); }
P operator*(T d) const { return P(x * d, y * d); }
P operator/(T d) const { return P(x / d, y / d); }
T dot(P p) const { return x * p.x + y * p.y; }
T cross(P p) const { return x * p.y - y * p.x; }
T cross(P a, P b) const { return (a - *this).cross(b - *this); }
T dist2() const { return x * x + y * y; }
double dist() const { return sqrt((double) dist2()); }
// angle to x-axis in interval [-pi, pi]
double angle() const { return atan2(y, x); }
P unit() const { return *this / dist(); } // makes dist()=1
P perp() const { return P(-y, x); } // rotates +90 degrees
P normal() const { return perp().unit(); }
// returns point rotated 'a' radians ccw around the origin
P rotate(double a) const { return P(x * cos(a) - y * sin(a), x * sin(a) + y * cos(a)); }
// friend ostream& operator<<(ostream& os, P p) { return os << "(" << p.x << "," << p.y << ")"; }
};
template <typename T>
string to_string(const Point<T>& p) {
string res = "(" + to_string(p.x) + ", " + to_string(p.y) + ")";
return res;
}
template <typename T>
class Fenwick {
public:
const int n;
const int max_power; // smallest power of 2 larger than n
vector<T> tree;
Fenwick(int _n) : n(_n), max_power(1 << (32 - __builtin_clz(n))), tree(n) {
assert(n > 0);
}
T get(int x) const {
assert(-1 <= x && x < n);
T res{};
while (x >= 0) {
res += tree[x];
x = (x & (x + 1)) - 1;
}
return res;
}
void modify(int x, T v) {
assert(0 <= x && x < n);
while (x < n) {
tree[x] += v;
x |= (x + 1);
}
}
};
using P = Point<long long>;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int xs, ys, xe, ye;
cin >> xs >> ys >> xe >> ye;
P s(xs, ys);
P e(xe, ye);
int n;
cin >> n;
vector<P> ps(n);
for (int i = 0; i < n; i++) {
int x, y;
cin >> x >> y;
ps[i] = P(x, y);
}
long long ans = 0;
int onL = 0;
int onR = 0;
for (P p : ps) {
if (s.cross(e, p) == 0) {
if ((e - s).dot(p - s) < 0) {
ans += onL;
onL += 1;
} else {
ans += onR;
onR += 1;
}
}
}
for (int rot = 0; rot < 2; rot++) {
vector<pair<P, int>> a;
for (P p : ps) {
if (s.cross(e, p) > 0) {
a.emplace_back(p, -1);
}
}
sort(a.begin(), a.end(), [&](auto pp, auto qq) {
P p = pp.first;
P q = qq.first;
long long cs = s.cross(p, q);
if (cs != 0) return cs > 0;
long long ce = e.cross(p, q);
return ce < 0;
});
int sz = a.size();
for (int i = 0; i < sz; i++) {
a[i].second = i;
}
sort(a.begin(), a.end(), [&](auto pp, auto qq) {
P p = pp.first;
P q = qq.first;
long long ce = e.cross(p, q);
if (ce != 0) return ce > 0;
long long cs = s.cross(p, q);
return cs < 0;
});
debug(a);
Fenwick<int> ft(sz + 1);
for (int z = sz - 1; z >= 0; z--) {
int i = a[z].second;
ans += ft.get(i);
ft.modify(i, +1);
}
swap(s, e);
}
cout << ans << '\n';
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3488kb
input:
0 0 1 0 2 -1 0 2 0
output:
0
result:
ok single line: '0'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3756kb
input:
0 0 1 0 4 -1 0 -2 0 2 0 3 0
output:
2
result:
ok single line: '2'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3696kb
input:
0 0 2 0 3 1 1 2 2 2 1
output:
2
result:
ok single line: '2'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3780kb
input:
0 0 2 0 3 1 1 0 2 0 1
output:
2
result:
ok single line: '2'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3504kb
input:
5 0 6 0 10 8 0 3 0 2 0 11 0 4 0 9 0 0 0 10 0 7 0 1 0
output:
20
result:
ok single line: '20'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3568kb
input:
0 0 1 0 3 1 1 1 2 1 3
output:
3
result:
ok single line: '3'
Test #7:
score: 0
Accepted
time: 0ms
memory: 3552kb
input:
0 0 4 3 2 5 0 3 0
output:
1
result:
ok single line: '1'
Test #8:
score: 0
Accepted
time: 0ms
memory: 3552kb
input:
0 0 4 3 2 3 0 5 0
output:
1
result:
ok single line: '1'
Test #9:
score: 0
Accepted
time: 0ms
memory: 3784kb
input:
-1000000000 1000000000 1000000000 999999999 2 -1000000000 -1000000000 999999999 999999998
output:
0
result:
ok single line: '0'
Test #10:
score: 0
Accepted
time: 0ms
memory: 3572kb
input:
999999999 -1000000000 1000000000 999999999 2 -1000000000 -1000000000 999999999 999999998
output:
1
result:
ok single line: '1'
Test #11:
score: 0
Accepted
time: 0ms
memory: 3592kb
input:
999999997 999999999 -999999998 -999999998 6 999999999 999999998 1000000000 999999997 999999997 999999996 -999999997 -999999997 -999999999 -999999999 -1000000000 -1000000000
output:
5
result:
ok single line: '5'
Test #12:
score: 0
Accepted
time: 0ms
memory: 3484kb
input:
-1000000000 -1000000000 -999999999 -999999999 9 1000000000 1000000000 999999999 999999999 999999998 999999998 1000000000 999999999 999999999 999999998 999999998 999999997 999999999 1000000000 999999998 999999999 999999997 999999998
output:
3
result:
ok single line: '3'
Test #13:
score: 0
Accepted
time: 0ms
memory: 3596kb
input:
-3 -15 15 3 6 0 4 -4 0 -5 1 -1 5 -2 2 -3 3
output:
3
result:
ok single line: '3'
Test #14:
score: 0
Accepted
time: 0ms
memory: 3780kb
input:
-2 -8 8 2 5 -4 1 0 2 -3 0 -1 3 -2 4
output:
4
result:
ok single line: '4'
Test #15:
score: 0
Accepted
time: 1ms
memory: 3640kb
input:
1399 -1293 -2636 1822 1000 -510452 -660980 -126684 -163868 -71237 -92045 -2084 -2468 -443168 -573824 -499861 -647261 -222626 -288146 -421363 -545579 -238824 -309128 -115470 -149342 -267482 -346250 -355325 -460037 -273089 -353513 -7691 -9731 -28873 -37169 -63138 -81554 -92419 -119483 -463727 -600455 ...
output:
499500
result:
ok single line: '499500'
Test #16:
score: 0
Accepted
time: 0ms
memory: 3704kb
input:
2024 48517 -6336 -100443 2500 4054 -20413 25109 -48138 21969 -16503 11444 -46388 16584 -7353 16289 -47643 18964 -35013 9659 -25643 13579 -25863 -2496 -49538 43629 -33448 37804 -32138 26494 -5943 35944 -47763 5739 -25423 17104 -50638 39984 -28328 34369 -40793 19239 -30113 40789 -49018 5794 -24443 384...
output:
2514840
result:
ok single line: '2514840'
Test #17:
score: 0
Accepted
time: 0ms
memory: 3620kb
input:
350 2230 1241 -7802 1000 2224211 195148 1335173 114349 406676 32803 429557 33916 2330996 203713 73715 4150 709541 58783 878180 74680 2148596 187513 2700437 235606 1901525 164650 809699 69517 640229 52627 2005331 175708 185060 13120 454100 37015 1171925 99850 2173301 188788 1715315 149950 1357061 116...
output:
426462
result:
ok single line: '426462'
Test #18:
score: 0
Accepted
time: 1ms
memory: 3664kb
input:
67176 -131382 -137128 265474 2500 -76892 101002 -36326 -5844 -67830 -30948 -63540 92326 -61326 16828 -156390 63408 -51544 86284 -23972 32726 -35526 1232 -160946 37738 -70122 51174 -53918 62848 -166448 54898 -170230 38512 -116262 106280 -91246 44742 -52920 15602 -36020 43184 -24538 5778 -93874 -32138...
output:
2511086
result:
ok single line: '2511086'
Test #19:
score: 0
Accepted
time: 1ms
memory: 3528kb
input:
-247940590 -800864001 -376339814 357558744 1000 -381895428 -268441834 587795571 401546767 -233436735 -505362442 -769956233 -716358227 -35039180 789288175 886928299 -255208074 695681326 548764540 -435121059 -552564037 605862324 -706572950 -80805696 -171753153 -589436010 -269238096 110878492 781059697...
output:
77951
result:
ok single line: '77951'
Test #20:
score: 0
Accepted
time: 0ms
memory: 3624kb
input:
-860607584 287988902 985877137 -539351386 1000 -764670345 -345617894 -814799418 382102043 -562999929 -588840592 -310568036 347625023 965238554 -434359700 -461802311 989074714 94823520 320962307 223908392 -512878157 614738982 917258490 -786355607 794417097 924310995 -659702530 467776168 981730793 344...
output:
129809
result:
ok single line: '129809'
Test #21:
score: 0
Accepted
time: 1ms
memory: 3596kb
input:
521581411 739623383 390644783 981463057 1000 -391006458 374559769 154426563 -275132165 -236790250 569582749 448348397 -125927455 615255336 -476931915 -739276549 583465455 -27192895 -700663448 -364210574 -142083415 -309883041 -788092341 -455439879 710860095 -293872280 -928496841 140528265 -352543210 ...
output:
29397
result:
ok single line: '29397'
Test #22:
score: 0
Accepted
time: 1ms
memory: 3836kb
input:
552761435 -490555112 -879584138 226903479 1000 513983008 -856379449 -282885476 -508469001 -745171212 149591233 619755720 646551250 -320598821 128919901 -357330351 606331257 -248486062 912374741 -737682030 -199060171 853127631 -773023298 554592416 90779243 -523709683 805183643 446660087 384838903 411...
output:
95569
result:
ok single line: '95569'
Test #23:
score: 0
Accepted
time: 1ms
memory: 3588kb
input:
-897511150 -912880529 -198952359 862342963 1000 -963176551 -855797925 66784798 797264821 -837598817 -449522820 -292776835 76738946 -627382553 -644087498 -328611844 -92057222 -997800004 -927373172 -475747625 -168423013 -824129218 45756981 576412504 -351703118 -60063496 -591759163 917806781 -231087597...
output:
159723
result:
ok single line: '159723'
Test #24:
score: 0
Accepted
time: 23ms
memory: 7828kb
input:
-936 1384 2229 -1676 100000 26508498 27417922 33854946 35016454 40397226 41783224 23221446 24018079 12719526 13155799 16760562 17335498 1345506 1391494 56127462 58053223 58319646 60320629 31799850 32890840 753090 778750 31054434 32119846 52876518 54690727 9501630 9827485 51477486 53243689 14237898 1...
output:
4999950000
result:
ok single line: '4999950000'
Test #25:
score: 0
Accepted
time: 29ms
memory: 7824kb
input:
309959 105267 -621041 -213933 99856 -287141 -104929 -249537 -173081 64091 -298829 -51549 -223481 -144033 -174145 -256117 -208193 -192781 -297093 -194405 -107085 -51213 -339457 -179061 -177393 -115893 -246637 -42589 -121841 22959 -239553 -128661 -324393 -195441 -100869 80191 -265929 -52137 -116353 -2...
output:
4021325705
result:
ok single line: '4021325705'
Test #26:
score: 0
Accepted
time: 35ms
memory: 7736kb
input:
1871 2344 -1715 -8260 100000 16271909 -5507284 228451853 -77258934 129191013 -43693620 105022569 -35520474 147028231 -49724634 224135373 -75801360 26637163 -9011472 215915345 -73021558 54064891 -18286824 128461265 -43446838 47964699 -16223896 37427853 -12661680 72162063 -24406822 57710739 -19519756 ...
output:
4279098242
result:
ok single line: '4279098242'
Test #27:
score: 0
Accepted
time: 36ms
memory: 7792kb
input:
-411017 -471193 824147 946115 99856 164187 329595 -225205 491071 148761 492873 -166949 351803 89553 673277 -344735 506741 -84045 753591 -1611 705409 -92729 839143 -131457 284947 -290997 358267 216615 370651 -340227 427457 294621 455133 -244269 359603 -20619 327673 -305249 306723 172977 222045 81545 ...
output:
4020181744
result:
ok single line: '4020181744'
Test #28:
score: 0
Accepted
time: 34ms
memory: 7868kb
input:
-493049606 142422915 655742603 782618345 100000 372659822 36814195 -879902865 -343445799 127638282 -960309469 863308440 841769357 940901285 -976514388 -218594602 -50498862 -35739019 112049913 556589337 169814314 30906963 200049188 558266258 -942958657 611608612 -117628688 -689574872 721981175 999907...
output:
920816082
result:
ok single line: '920816082'
Test #29:
score: 0
Accepted
time: 35ms
memory: 7772kb
input:
-565624827 -392213290 -945987758 531083970 100000 427815104 763037097 560913615 88030150 -938721528 125754351 401971882 -292860838 265885527 233571806 -697661840 -882461658 -249482289 -9217592 521611560 170526745 938180751 -961491915 457205737 -781551578 -195128877 -643111288 240952815 -567462266 98...
output:
906858623
result:
ok single line: '906858623'
Test #30:
score: 0
Accepted
time: 31ms
memory: 7792kb
input:
466300583 993922912 -127152168 923574549 100000 -384613699 161915014 427022701 -333003148 -609781757 -518791711 466446801 -48144179 773328349 -242623748 122863668 528104347 -268413401 -801720289 -377069295 244415878 519926826 -191733167 -357257785 -418047622 337616740 67972521 -945491575 314030073 -...
output:
700078265
result:
ok single line: '700078265'
Test #31:
score: 0
Accepted
time: 34ms
memory: 7884kb
input:
-501578953 567714234 195739451 852596079 100000 62051165 -260998972 477333459 156105251 -541274218 859443758 -481156517 -36380569 -927287282 166632916 -201758090 -477810652 548947894 285382678 658062637 417884781 -268660582 828181675 -332432467 -840580164 136620341 -490053508 845233246 418675163 -99...
output:
713954645
result:
ok single line: '713954645'
Test #32:
score: 0
Accepted
time: 39ms
memory: 7372kb
input:
219637968 192991173 -698402753 -601819272 100000 259660371 -528498337 -397772803 415807368 359873454 -948237995 -827873249 -20799427 -828528818 834782384 901589261 132912376 -213862144 -790488359 -942804323 211673794 899073910 868118020 566268640 -541301393 190752646 -244675398 -685741568 200069916 ...
output:
719408904
result:
ok single line: '719408904'
Test #33:
score: 0
Accepted
time: 1ms
memory: 3808kb
input:
-1000000000 -1000000000 1000000000 999999999 500 -350442638 -350442637 568220162 568220163 753240085 753240086 -863721429 -863721428 430486966 430486967 -179196196 -179196195 -256564629 -256564628 -187878036 -187878035 -973876016 -973876015 981508231 981508232 999999999 999999998 999260402 999260403...
output:
0
result:
ok single line: '0'
Test #34:
score: 0
Accepted
time: 22ms
memory: 7796kb
input:
-1000000000 -1000000000 1000000000 999999999 100000 -943241323 -943241322 404514203 404514204 -567803030 -567803029 -504275693 -504275692 73228341 73228342 -857463850 -857463849 -556392158 -556392157 -44505729 -44505728 -430072494 -430072493 -606800265 -606800264 18284690 18284691 -442907772 -442907...
output:
0
result:
ok single line: '0'
Test #35:
score: 0
Accepted
time: 29ms
memory: 7280kb
input:
0 0 1 1 99458 999999780 999999981 -999999820 -999999955 -999999864 -999999815 -999999840 -999999920 999999961 999999845 -999999917 -999999941 999999831 999999780 999999787 999999790 -999999944 -999999794 -999999858 -999999973 999999803 999999853 999999923 999999933 -999999975 -999999966 -999999936 -...
output:
49506
result:
ok single line: '49506'
Test #36:
score: 0
Accepted
time: 0ms
memory: 3776kb
input:
-5 -45 45 5 10 -9 2 -1 7 -3 5 -2 9 -8 0 0 8 -7 1 -6 3 -5 4 -4 6
output:
5
result:
ok single line: '5'
Test #37:
score: 0
Accepted
time: 0ms
memory: 3568kb
input:
-25 -1225 1225 25 50 -35 47 -15 13 -18 45 -9 44 -42 23 -1 41 -41 43 -16 37 -7 11 -22 0 -45 27 -24 29 -6 28 -44 32 -48 10 -46 8 -30 5 -31 26 -27 46 -17 34 0 18 -3 48 -2 22 -14 21 -40 24 -12 40 -4 17 -28 36 -43 38 -36 39 -26 49 -25 6 -33 9 -21 15 -37 1 -19 4 -49 7 -34 14 -13 30 -23 2 -11 12 -38 31 -39...
output:
569
result:
ok single line: '569'
Test #38:
score: 0
Accepted
time: 1ms
memory: 3572kb
input:
-250 -124750 124750 250 500 -381 186 -464 17 -314 346 -384 397 -335 245 -67 177 -385 252 -414 325 -366 164 -115 38 -42 436 -421 374 -306 386 -52 225 -198 480 -450 305 -186 273 -53 454 -495 459 -235 211 -123 161 -212 139 -151 323 -313 73 -59 364 -114 215 -197 406 -101 413 -496 498 -238 399 -27 7 -233...
output:
63329
result:
ok single line: '63329'
Test #39:
score: 0
Accepted
time: 2ms
memory: 3764kb
input:
-2500 -12497500 12497500 2500 5000 -966 4004 -4827 3204 -1060 4687 -558 676 -3475 4845 -2417 16 -3387 3107 -2089 4017 -1651 39 -3628 1424 -3003 4278 -3961 4388 -2666 1096 -3927 1014 -2377 3313 -1015 1237 -4906 1917 -1844 2471 -1560 2537 -3268 4424 -1935 135 -1804 4646 -1484 802 -905 1320 -2552 4197 ...
output:
6334021
result:
ok single line: '6334021'
Test #40:
score: 0
Accepted
time: 3ms
memory: 3848kb
input:
-5000 -49995000 49995000 5000 10000 -2210 7653 -8372 8009 -4154 6193 -1745 1427 -6355 8119 -556 2170 -665 8336 -7655 5038 -2545 8155 -74 4214 -1929 2030 -5531 7539 -8540 4882 -3486 3361 -8233 1272 -4287 3148 -1911 7956 -8358 1886 -6989 1582 -5901 4723 -6777 9562 -4305 6188 -5512 3360 -4902 236 -7408...
output:
24918541
result:
ok single line: '24918541'
Test #41:
score: 0
Accepted
time: 13ms
memory: 5576kb
input:
-22360 -999939200 999939200 22360 44721 -17987 25781 -35172 42716 -11654 33760 -44372 6757 -39878 8060 -12379 36777 -28349 4396 -35579 35011 -33929 683 -16304 17015 -14490 29892 -30885 20514 -18600 18276 -41056 29332 -32185 28564 -32899 22955 -37751 29324 -39524 24341 -8246 12557 -750 37586 -4316 95...
output:
499009056
result:
ok single line: '499009056'
Test #42:
score: 0
Accepted
time: 14ms
memory: 5548kb
input:
-100000 0 0 -100000 50000 90090 183551 1186309 1215227 78278 145386 297093 297471 35768 87915 2634370 2629917 182962 87769 27102 31974 2463785 2371347 21366 51384 50893 126210 74748 54937 118399 102753 31382 72846 89239 132418 264827 267651 4670 13565 122265 124224 351712 405014 50889 30271 1381 530...
output:
628250796
result:
ok single line: '628250796'
Test #43:
score: 0
Accepted
time: 27ms
memory: 7492kb
input:
-150000 0 0 -150000 75000 95064 11345 441747 410033 57489 157559 116276 96417 64333 174847 128067 183750 8382 113475 267214 417125 83986 103194 151271 47537 214008 321341 75027 30829 714707 652393 259060 398577 49349 86844 379688 252661 285728 228769 104668 5626 107316 1462 454521 597911 18409 41206...
output:
1411420544
result:
ok single line: '1411420544'
Test #44:
score: 0
Accepted
time: 35ms
memory: 7804kb
input:
-200000 0 0 -200000 100000 2005480 1828585 331863 263315 238793 154293 185661 200347 262251 134039 43236 166751 143507 251464 148940 28048 330827 391894 34447 87486 107198 71270 365766 475968 540963 727307 244813 374773 53819 186600 46784 101154 387395 279213 306787 114402 774621 770497 129937 18962...
output:
2499620812
result:
ok single line: '2499620812'
Test #45:
score: 0
Accepted
time: 36ms
memory: 7776kb
input:
-200000 0 0 -200000 100000 240312 237249 204917 72019 130505 279905 1000785 922876 106777 109489 302429 227691 205081 17739 230176 104296 214883 175433 5411 19321 218333 61474 23934 30424 234531 222258 124849 292852 848516 972582 233028 279796 149545 207602 106674 271238 244764 218944 402621 314677 ...
output:
2502753353
result:
ok single line: '2502753353'
Test #46:
score: 0
Accepted
time: 35ms
memory: 7848kb
input:
-200000 0 0 -200000 100000 94114 102249 16466 44152 224856 30539 306991 224937 27182 18929 176375 5405 48403 117939 327599 185520 87307 14730 92510 30240 142564 14391 638225 452382 67610 54250 889806 725397 31521 105879 4673827 4773426 36899 64434 843841 1028423 334059 268263 50135 24316 127711 3944...
output:
2496106088
result:
ok single line: '2496106088'
Test #47:
score: 0
Accepted
time: 28ms
memory: 7688kb
input:
-200000 0 0 -200000 100000 164847 307409 122253 113984 155409 15553 477371 481929 153570 148697 280050 167062 307271 155342 212246 210200 60606 44598 3887 157915 283201 331693 215724 273546 62920 117762 151511 257418 171548 39332 88477 120953 243363 124168 110955 46802 128553 33470 126455 18494 1586...
output:
2500121148
result:
ok single line: '2500121148'