QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#674278#5079. Empty QuadrilateralsKowerKointAC ✓1984ms4308kbC++205.3kb2024-10-25 14:54:532024-10-25 14:54:59

Judging History

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

  • [2024-10-25 14:54:59]
  • 评测
  • 测评结果:AC
  • 用时:1984ms
  • 内存:4308kb
  • [2024-10-25 14:54:53]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct P { ll x; ll y; };

P diff(P a, P b) {
  return {b.x-a.x, b.y-a.y};
}

ll cross(P a, P b) {
  return a.x*b.y - a.y*b.x;
}

ll dot(P a, P b) {
  return a.x*b.x + a.y*b.y;
}

int naive(int n, vector<P> points) {
  auto triangle_include = [&](P p, P q, P r, P x) {
    p = diff(x, p);
    q = diff(x, q);
    r = diff(x, r);
    if(cross(p, q) > 0 && cross(q, r) > 0 && cross(r, p) > 0) return true;
    if(cross(p, q) < 0 && cross(q, r) < 0 && cross(r, p) < 0) return true;
    return false;
  };
  int ans = 0;
  for(int i = 0; i < n; i++) for(int j = 0; j < i; j++) for(int k = 0; k < j; k++) for(int l = 0; l < k; l++) {
    array<P, 4> poly = {points[i], points[j], points[k], points[l]};
    bool valid = true;
    for(int x = 0; x < n; x++) {
      if(x == i) continue;
      if(x == j) continue;
      if(x == k) continue;
      if(x == l) continue;
      int cnt = 0;
      for(int u = 0; u < 4; u++) for(int v = 0; v < u; v++) for(int w = 0; w < v; w++) {
        if(triangle_include(poly[u], poly[v], poly[w], points[x])) cnt++;
      }
      if(cnt == 2) valid = false;
    }
    if(valid) ans++;
  }
  return ans;
}

int solve(int n, vector<P> points) {
  auto triangle_include = [&](P p, P q, P r, P x) {
    p = diff(x, p);
    q = diff(x, q);
    r = diff(x, r);
    if(cross(p, q) > 0 && cross(q, r) > 0 && cross(r, p) > 0) return true;
    if(cross(p, q) < 0 && cross(q, r) < 0 && cross(r, p) < 0) return true;
    return false;
  };
  auto between = [&](int i, int j) {
    if(points[i].x > points[j].x) swap(i, j);
    int ret = 0;
    for(int k = 0; k < n; k++) {
      if(points[k].x <= points[i].x) continue;
      if(points[j].x <= points[k].x) continue;
      if(cross(diff(points[i], points[k]), diff(points[i], points[j])) > 0) ret++;
    }
    return ret;
  };
  vector bet(n, vector<int>(n));
  for(int i = 0; i < n; i++) for(int j = i+1; j < n; j++) {
    bet[i][j] = bet[j][i] = between(i, j);
  }
  map<ll, vector<int>> xi;
  for(int i = 0; i < n; i++) {
    xi[points[i].x].push_back(i);
  }
  for(auto& [k, v] : xi) {
    sort(v.begin(), v.end(), [&](int i, int j) { return points[i].y < points[j].y; });
  }
  vector<int> below(n);
  for(int i = 0; i < n; i++) {
    const auto& xv = xi[points[i].x];
    below[i] = lower_bound(xv.begin(), xv.end(), i, [&](int i, int j) { return points[i].y < points[j].y; }) - xv.begin();
  }
  auto valid_triangle = [&](int i, int j, int k) {
    array<int, 3> is = {i, j, k};
    sort(is.begin(), is.end(), [&](int i, int j) { return points[i].x < points[j].x; });
    int inner = 0;
    inner += bet[is[0]][is[2]] - bet[is[0]][is[1]] - bet[is[1]][is[2]];
    const auto& xv = xi[points[is[1]].x];
    if(points[is[0]].x < points[is[1]].x && points[is[1]].x < points[is[2]].x) {
      if(cross(diff(points[is[0]], points[is[1]]), diff(points[is[0]], points[is[2]])) > 0) {
        inner -= below[is[1]] + 1;
      } else {
        inner -= below[is[1]];
      }
    }
    return inner == 0;
  };
  ll all = 0, not_convex = 0;
  for(int i = 0; i < n; i++) for(int j = i+1; j < n; j++) {
    vector<int> valid_oppos;
    for(int k = 0; k < n; k++) {
      if(k == i) continue;
      if(k == j) continue;
      if(valid_triangle(i, j, k)) valid_oppos.push_back(k);
    }
    auto a = points[i], b = points[j];
    auto arg_cmp = [&](P p, P q, P start) {
      ll pc = cross(start, p);
      ll qc = cross(start, q);
      bool p_0 = pc == 0 && dot(p, start) > 0;
      bool q_0 = qc == 0 && dot(q, start) > 0;
      if(p_0 && q_0) return false;
      if(p_0 && !q_0) return true;
      if(!p_0 && q_0) return false;
      int pp = pc > 0 ? 0 : pc == 0 ? 1 : 2;
      int qp = qc > 0 ? 0 : pc == 0 ? 1 : 2;
      if(pp != qp) return pp < qp;
      return cross(p, q) > 0;
    };
    vector<int> by_b = valid_oppos;
    sort(by_b.begin(), by_b.end(), [&](int x, int y) { return arg_cmp(diff(b, points[x]), diff(b, points[y]), diff(b, a)); });
    vector<int> by_a = valid_oppos;
    sort(by_a.begin(), by_a.end(), [&](int x, int y) { return arg_cmp(diff(a, points[x]), diff(a, points[y]), diff(a, b)); });
    auto is_above = [&](int k) {
      return cross(diff(a, b), diff(a, points[k])) > 0;
    };
    int num_above = 0;
    for(int k : valid_oppos) {
      if(is_above(k)) num_above++;
    }
    int b_start = 0;
    while(b_start < by_b.size() && !is_above(by_b[b_start])) b_start++;
    int a_end = 0;
    while(a_end < by_a.size() && is_above(by_a[a_end])) a_end++;
    for(int k : valid_oppos) {
      if(is_above(k)) continue;
      all += num_above;
    }
    {
      int j = b_start;
      for(int bi = 0; bi < b_start; bi++) {
        auto c = points[by_b[bi]];
        while(j < by_b.size() && cross(diff(b, c), diff(b, points[by_b[j]])) > 0) j++;
        not_convex += j - b_start;
      }
    }
    {
      int j = 0;
      for(int ai = a_end; ai < by_a.size(); ai++) {
        auto c = points[by_a[ai]];
        while(j < by_a.size() && cross(diff(a, c), diff(a, points[by_a[j]])) > 0) j++;
        not_convex += a_end - j;
      }
    }
  }
  return all - (all-not_convex)/2;
}

int main() {
  int n; cin >> n;
  vector<P> points(n);
  for(int i = 0; i < n; i++) cin >> points[i].x >> points[i].y;
  cout << solve(n, points) << endl;
}


Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3608kb

input:

5
0 0
2 4
6 2
6 -2
7 3

output:

8

result:

ok single line: '8'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3556kb

input:

4
0 0
10 0
5 10
3 2

output:

3

result:

ok single line: '3'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3596kb

input:

10
10 10
1 0
4 8
-1 -4
-7 -4
-3 2
5 -10
-10 -5
1 1
5 -3

output:

170

result:

ok single line: '170'

Test #4:

score: 0
Accepted
time: 0ms
memory: 3464kb

input:

1
0 0

output:

0

result:

ok single line: '0'

Test #5:

score: 0
Accepted
time: 0ms
memory: 3756kb

input:

2
0 0
1 0

output:

0

result:

ok single line: '0'

Test #6:

score: 0
Accepted
time: 0ms
memory: 3752kb

input:

3
0 0
1 0
10 10

output:

0

result:

ok single line: '0'

Test #7:

score: 0
Accepted
time: 0ms
memory: 3616kb

input:

4
0 0
1 0
1 1
0 1

output:

1

result:

ok single line: '1'

Test #8:

score: 0
Accepted
time: 0ms
memory: 3592kb

input:

4
-1000000000 1000000000
1000000000 1000000000
1000000000 -1000000000
-1000000000 -1000000000

output:

1

result:

ok single line: '1'

Test #9:

score: 0
Accepted
time: 0ms
memory: 3596kb

input:

4
-8 -3
1 1
7 0
-10 1

output:

1

result:

ok single line: '1'

Test #10:

score: 0
Accepted
time: 0ms
memory: 3624kb

input:

5
-5 8
-7 6
8 9
-8 -7
3 1

output:

5

result:

ok single line: '5'

Test #11:

score: 0
Accepted
time: 0ms
memory: 3624kb

input:

10
-82 -34
9 -90
-67 13
80 -31
-45 51
28 90
-90 -75
58 33
-12 71
90 -80

output:

210

result:

ok single line: '210'

Test #12:

score: 0
Accepted
time: 62ms
memory: 3648kb

input:

100
3759 9658
2910 -9943
4170 9478
-7675 -6575
-6661 7820
6123 8295
9859 -498
9799 42
-2324 -9578
-6860 7649
2269 -9996
8777 4515
8363 5630
6479 8015
-9991 -1944
8574 -7477
8687 -7393
7206 7266
5208 8983
-9081 -4460
-4262 9116
9722 651
9881 -5725
-4899 8911
9867 -592
-7206 7053
-3828 -9346
7471 6976...

output:

3921225

result:

ok single line: '3921225'

Test #13:

score: 0
Accepted
time: 574ms
memory: 3724kb

input:

203
-980345 -265686
-146271 -978033
917841 -441678
-916267 446738
-928177 -428655
850137 -573235
-525140 -879110
-563115 -865718
19693 999740
-304353 -948387
287100 -986973
-329294 -941062
936446 -395687
-933810 -415914
-27770 -989661
120040 -999643
899311 -480711
793647 625727
999790 7708
991740 -1...

output:

68685050

result:

ok single line: '68685050'

Test #14:

score: 0
Accepted
time: 1984ms
memory: 3988kb

input:

300
-109565666 -999084112
987010217 283882659
902175413 602257050
-649185052 919125832
776751215 -617742367
-997974804 287676067
-880568072 -587807228
-537465923 -936971665
-75548128 -997577354
-43885301 997630537
155312299 -972230096
-882508267 -583190585
-562836073 946534352
14128786 994305968
591...

output:

330791175

result:

ok single line: '330791175'

Test #15:

score: 0
Accepted
time: 1ms
memory: 3600kb

input:

4
-1 0
0 1
0 0
1 -1

output:

3

result:

ok single line: '3'

Test #16:

score: 0
Accepted
time: 1ms
memory: 3524kb

input:

4
-1000000 0
0 1000000
0 0
1000000 -1000000

output:

3

result:

ok single line: '3'

Test #17:

score: 0
Accepted
time: 1ms
memory: 3756kb

input:

5
-6 3
4 0
0 0
1 3
0 -1

output:

8

result:

ok single line: '8'

Test #18:

score: 0
Accepted
time: 1ms
memory: 3828kb

input:

5
-1 -2
1 0
3 1
5 0
1 4

output:

9

result:

ok single line: '9'

Test #19:

score: 0
Accepted
time: 0ms
memory: 3824kb

input:

6
0 -4
2 4
8 -1
-2 0
6 -2
5 -3

output:

18

result:

ok single line: '18'

Test #20:

score: 0
Accepted
time: 1ms
memory: 3552kb

input:

6
0 -4
2 4
8 -1
-2 0
6 -1
5 -3

output:

19

result:

ok single line: '19'

Test #21:

score: 0
Accepted
time: 1ms
memory: 3600kb

input:

6
0 -4
2 4
8 -1
-2 0
1 -1
5 -3

output:

20

result:

ok single line: '20'

Test #22:

score: 0
Accepted
time: 1ms
memory: 3616kb

input:

6
0 5
5 5
5 0
1 2
4 3
0 0

output:

22

result:

ok single line: '22'

Test #23:

score: 0
Accepted
time: 1ms
memory: 3596kb

input:

7
-63 100
51 -100
100 50
50 92
44 -96
0 90
-100 36

output:

37

result:

ok single line: '37'

Test #24:

score: 0
Accepted
time: 0ms
memory: 3488kb

input:

7
-63 100
51 -100
100 50
50 92
44 -96
40 80
-100 36

output:

38

result:

ok single line: '38'

Test #25:

score: 0
Accepted
time: 0ms
memory: 3600kb

input:

7
-63 100
51 -100
100 50
50 92
44 -96
0 0
-100 36

output:

39

result:

ok single line: '39'

Test #26:

score: 0
Accepted
time: 0ms
memory: 3600kb

input:

7
0 -40
20 40
80 -10
-20 00
60 -20
0 0
50 -30

output:

40

result:

ok single line: '40'

Test #27:

score: 0
Accepted
time: 1ms
memory: 3592kb

input:

7
0 -40
20 40
80 -10
-20 00
60 -10
0 0
50 -30

output:

42

result:

ok single line: '42'

Test #28:

score: 0
Accepted
time: 1ms
memory: 3816kb

input:

7
0 -40
20 40
80 -10
-20 00
60 -10
20 0
50 -30

output:

42

result:

ok single line: '42'

Test #29:

score: 0
Accepted
time: 0ms
memory: 3620kb

input:

7
0 -40
20 40
80 -10
-20 00
10 -10
20 0
50 -30

output:

40

result:

ok single line: '40'

Test #30:

score: 0
Accepted
time: 0ms
memory: 3596kb

input:

7
0 -40
20 40
80 -10
-20 00
40 -10
0 0
50 -30

output:

42

result:

ok single line: '42'

Test #31:

score: 0
Accepted
time: 0ms
memory: 3556kb

input:

7
-20 30
40 -10
50 30
20 20
40 10
30 0
80 0

output:

42

result:

ok single line: '42'

Test #32:

score: 0
Accepted
time: 0ms
memory: 3756kb

input:

9
-1000000 1000000
1000000 1000000
1000000 -1000000
-1000000 -1000000
-1 -2
1 0
3 1
5 0
1 4

output:

113

result:

ok single line: '113'

Test #33:

score: 0
Accepted
time: 929ms
memory: 3960kb

input:

300
0 -40
20 40
80 -10
-20 00
60 -20
0 0
50 -30
3759 9658
2910 -9943
4170 9478
-7675 -6575
-6661 7820
6123 8295
9859 -498
9799 42
-2324 -9578
-6860 7649
2269 -9996
8777 4515
8363 5630
6479 8015
-9991 -1944
8574 -7477
8687 -7393
7206 7266
5208 8983
-9081 -4460
-4262 9116
9722 651
9881 -5725
-4899 891...

output:

48777998

result:

ok single line: '48777998'

Test #34:

score: 0
Accepted
time: 896ms
memory: 4100kb

input:

300
-63 100
51 -100
100 50
50 92
44 -96
0 0
-100 36
3759 9658
2910 -9943
4170 9478
-7675 -6575
-6661 7820
6123 8295
9859 -498
9799 42
-2324 -9578
-6860 7649
2269 -9996
8777 4515
8363 5630
6479 8015
-9991 -1944
8574 -7477
8687 -7393
7206 7266
5208 8983
-9081 -4460
-4262 9116
9722 651
9881 -5725
-4899...

output:

45037874

result:

ok single line: '45037874'

Test #35:

score: 0
Accepted
time: 206ms
memory: 3752kb

input:

200
7006 -177
3756 -39
9872 -2618
8860 -8435
8567 -8858
3007 -9855
6431 -78
9573 -1996
645 -7499
3665 -9945
8083 -9316
4098 -11
8951 -1249
5575 -9951
8726 -1037
537 -1720
5520 -9957
9963 -4363
2960 -124
2250 -218
129 -5825
2687 -9786
6657 -9789
4055 -9977
9876 -5238
1496 -746
1577 -8771
2099 -290
12...

output:

9540323

result:

ok single line: '9540323'

Test #36:

score: 0
Accepted
time: 442ms
memory: 4208kb

input:

300
-501908338 -342208696
-10167056 -346610906
-674262068 -513861820
740719799 -20856381
668020647 118853908
-594640750 -576677796
300321882 646151426
-253013235 593016512
902927188 793410806
-301044865 318724915
-486058015 -496110017
-351177263 -743387574
807088372 54542457
208214529 -524493165
-69...

output:

2795836

result:

ok single line: '2795836'

Test #37:

score: 0
Accepted
time: 455ms
memory: 4208kb

input:

300
-482422458 -650575249
739358757 -239520925
-788783744 -570062901
-418837911 -745067752
423436230 819110878
841974335 -613836194
-768284217 720559856
-358549450 -256316335
291277639 -897729580
-110268594 -700475931
175686758 -367088054
-530875306 258552250
-212148201 -472842853
503829688 -1360053...

output:

2814628

result:

ok single line: '2814628'

Test #38:

score: 0
Accepted
time: 443ms
memory: 4052kb

input:

300
356181715 89939368
-72443051 -704507906
-690966591 -279739694
-976538108 -341475796
93551668 -148779235
251274485 -116441701
849551224 -933105925
221551672 -277806162
411595935 -508423498
-490878234 -526198472
901722131 -943273082
-34626519 -349420547
664149659 -282364112
188299626 -41569992
-51...

output:

2708850

result:

ok single line: '2708850'

Test #39:

score: 0
Accepted
time: 461ms
memory: 4060kb

input:

300
31840392 166106964
358911007 869126535
-621777650 -300184792
-67883155 -75407554
322946753 327310839
278025305 248174787
-126604649 -128856871
726704839 641989969
-321890281 428431976
-4185200 870480695
65151553 948684572
157543013 327022326
-432953230 59313390
130872597 499753387
186866250 7853...

output:

2745119

result:

ok single line: '2745119'

Test #40:

score: 0
Accepted
time: 448ms
memory: 4048kb

input:

300
-4385121 -503122347
734999363 642635536
515185589 -470338969
375650132 185233124
477179262 101130709
1000000000 1000000000
347997647 -1000000000
-660477475 -261237081
920751336 820224292
524777849 -49304657
580674293 -194540800
748256112 384808467
112178604 145725198
310736009 -631543545
6096309...

output:

2698071

result:

ok single line: '2698071'

Test #41:

score: 0
Accepted
time: 455ms
memory: 4248kb

input:

300
203045772 308711983
-916118373 318797670
-41260195 -986552053
637476708 950931779
-528765585 -353147471
990296819 98284627
-699115850 782110838
890436583 703447789
-229547159 -709125382
975139869 169993037
509469330 110669354
-675216600 637346207
-953801852 327918372
-22772314 -249145451
9276083...

output:

2796264

result:

ok single line: '2796264'

Test #42:

score: 0
Accepted
time: 470ms
memory: 4256kb

input:

300
-944766581 480214191
-248842272 -753277593
-448997872 -482488443
-996752701 -260550745
-204818531 281299141
233897455 758175732
688878436 765531134
-823381320 -303603411
403496227 89922133
-357366993 320790475
-1000000000 -59389753
-658015306 826763677
538496279 900395547
703071549 677054086
-45...

output:

3509126

result:

ok single line: '3509126'

Test #43:

score: 0
Accepted
time: 501ms
memory: 4004kb

input:

300
-182831980 -969196441
414272271 951848039
-548245229 -783948441
801132021 -563171314
-345329194 -598054683
-305508089 -924826054
-218220807 -526211105
-461925755 -713550422
507769882 -860203633
-47508636 999965834
653109611 -727477703
-269444125 -940959595
-230881125 -955536641
569600375 5562516...

output:

4762046

result:

ok single line: '4762046'

Test #44:

score: 0
Accepted
time: 610ms
memory: 4084kb

input:

300
-771154090 780208833
-885146379 618774890
-929480005 524450406
988987341 -251030240
-528198190 935166148
916434667 495090115
-971988142 -123463555
927578054 473068874
-296540818 995693336
-974419944 401991872
-286359667 -324153147
-434454895 963693999
960637514 -395444073
789192595 -780327590
18...

output:

9910427

result:

ok single line: '9910427'

Test #45:

score: 0
Accepted
time: 1004ms
memory: 4068kb

input:

300
771496631 -715636432
-284370823 -992031886
221646111 -984376736
-502926656 942054170
957030786 250826089
-724998045 856842554
477328838 -923763580
-186630182 990308507
-996566153 -79000362
-997774710 161151873
330239361 976675527
-927892928 -428119195
975961758 153079132
880348453 495048261
6464...

output:

45124100

result:

ok single line: '45124100'

Test #46:

score: 0
Accepted
time: 1593ms
memory: 4308kb

input:

300
-999157963 -18189049
495673938 -900812371
695856806 879843169
-646890746 843856158
-607964011 -861384114
-642823118 846244239
-843220933 678715057
999228694 348303755
-866562377 -584734435
-987109903 -216026832
1000000000 336971228
-758379032 -733372125
-407150315 945513929
969993871 485721162
8...

output:

146429294

result:

ok single line: '146429294'

Test #47:

score: 0
Accepted
time: 1951ms
memory: 4004kb

input:

300
-884798186 738312829
-878931221 747555150
-975559797 -87153305
90984653 986432102
948135107 239847165
-972411704 479962936
-457628206 -898161096
189527452 965324546
685266767 -798324643
702689516 701905705
726151515 -764601703
-951644487 -184972102
770505738 609751583
296791271 934118777
8649066...

output:

262517341

result:

ok single line: '262517341'