QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#674278 | #5079. Empty Quadrilaterals | KowerKoint | AC ✓ | 1984ms | 4308kb | C++20 | 5.3kb | 2024-10-25 14:54:53 | 2024-10-25 14:54:59 |
Judging History
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'