QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#407578#2297. Flatland OlympicsAndycipationAC ✓39ms7884kbC++203.8kb2024-05-09 00:21:172024-05-09 00:21:18

Judging History

你现在查看的是最新测评结果

  • [2024-05-09 00:21:18]
  • 评测
  • 测评结果:AC
  • 用时:39ms
  • 内存:7884kb
  • [2024-05-09 00:21:17]
  • 提交

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'