QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#814547#9882. Two Convex Setsucup-team3161#TL 3008ms729620kbC++175.5kb2024-12-14 18:11:572024-12-14 18:11:57

Judging History

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

  • [2024-12-14 18:11:57]
  • 评测
  • 测评结果:TL
  • 用时:3008ms
  • 内存:729620kb
  • [2024-12-14 18:11:57]
  • 提交

answer

// what is matter? never mind. 
#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,sse4,popcnt,abm,mmx,avx,avx2")
#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
#define ll long long
#define ull unsigned long long
#define int long long
#define SZ(x) ((int)((x).size()))
#define ALL(x) (x).begin(),(x).end()
using namespace std;
inline int read()
{
	char c=getchar();int x=0;bool f=0;
	for(;!isdigit(c);c=getchar())f^=!(c^45);
	for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
	return f?-x:x;
}

#define fi first
#define se second
#define pb push_back
#define mkp make_pair
typedef pair<int,ll>pii;
typedef vector<int>vi;

typedef double db;
const db eps=1e-8,pi=3.14159265358979323846;
int sgn(int x){return x<0?-1:x>0;}
int cmp(int a,int b){return sgn(a-b);}

struct P{
	int x,y;
	P(int x=0,int y=0):x(x),y(y){}
	P&operator +=(P o){return x+=o.x,y+=o.y,*this;}
	P&operator -=(P o){return x-=o.x,y-=o.y,*this;}
	P&operator *=(int o){return x*=o,y*=o,*this;}
	P&operator /=(int o){return x/=o,y/=o,*this;}
	friend P operator +(P a,P b){return a+=b;}
	friend P operator -(P a,P b){return a-=b;}
	friend P operator *(P a,int b){return a*=b;}
	friend P operator /(P a,int b){return a/=b;}
	friend bool operator <(P a,P b){return fabs(a.x-b.x)<eps?a.y<b.y:a.x<b.x;}
	friend bool operator ==(P a,P b){return cmp(a.x,b.x)==0 && cmp(a.y,b.y)==0;}
	friend bool operator !=(P a,P b){return !(a==b);}
	friend int operator %(P a,P b){return a.x*b.x+a.y*b.y;} // dot
	friend int operator *(P a,P b){return a.x*b.y-a.y*b.x;} // cross
	
	P rot90(){return P(-y,x);}
	db ang(){return atan2(y,x);}
	db len(){return sqrt(x*x+y*y);}
	int len2(){return x*x+y*y;}
	
	int half(){return sgn(y)==1||(sgn(y)==0&&sgn(x)>=0);}
//	P unit(){return ((*this))/len();}
	
	void read(){cin>>x>>y;}
	void out(){cout<<"("<<x<<","<<y<<")"<<endl;}
};
bool cmp_dir(P a,P b){
	if(a.half()!=b.half())return a.half()<b.half();
	return sgn(a*b)>0;
}

db dis(P a,P b){return (a-b).len();}
int cross(P a,P b,P c){
	// (a->b)*(a->c)
	return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}
int cmp3(P a,P b,P c){
	return sgn(cross(a,b,c));
}

#define maxn 20000005
#define inf 0x3f3f3f3f3f3f3f3f

int n;
P p[maxn];
int dr[45][45][45];

#undef int
struct hshMap {
    static const int mod = 19260817;
    struct node {
        ll key; int val, nxt;
    } a[maxn];
    int cnt, tot, head[19260817];
    inline int calc(unsigned long long x) {
        int xx = x % mod;
        for (int i = head[xx]; i; i = a[i].nxt) {
            if (a[i].key == x) return a[i].val;
        }
        ++cnt;
        a[++tot] = {x, cnt, head[xx]};
        head[xx] = tot;
        return cnt;
    }
    void clear(){
        tot=0;
        memset(head,0,sizeof head);
    }
} mp;
#define int long long
int f[maxn],g[maxn];

#define node array<char,8> 
int tot;
node sts[maxn],lsts[maxn];
int ID(node o){
    ll S=0;
    For(i,0,7) S=S*(n+5)+(o[i]+1);
    int id=mp.calc(S);
    //cout<<"id,tot "<<id<<" "<<tot<<endl;
    if(id>tot){ ++tot; sts[tot]=o;} 
    return id;
}

node fir;

void upd(node&a,int x){
   // cout<<"addx: "<<x<<"\n"; For(i,0,7) cout<<a[i]<<" "; cout<<"\n";
    g[ID(a)]+=x;
}

signed main()
{
  //  freopen("my.out","w",stdout);
    cin>>n;
    For(i,1,n) cin>>p[i].x>>p[i].y;
    sort(p+1,p+n+1);
    For(i,1,n) For(j,1,n) For(k,1,n) {
        dr[i][j][k]=cmp3(p[i],p[j],p[k]);
    }

    
 //   cout<<"dir: "<<dr[1][2][3]<<" "<<dr[2][3][4]<<" "<<dr[1][3][4]<<endl;
	
    fir[0]=fir[1]=fir[2]=fir[3]=1;
    upd(fir,1);
    swap(f[1],g[1]);

    int L=1,R=1;

    For(i,2,n){

        int ntot=tot;
     //   cout<<"tot "<<tot<<endl;
    //    cout<<"Add "<<i<<" ---------------------------\n";
        mp.clear();
        mp.cnt=0; tot=0;
        For(j,1,ntot) lsts[j]=sts[j];
        For(j,1,ntot){
            node u=lsts[j];
        //    cout<<"trs "<<j<<" "<<f[j]<<endl;
       //     cout<<"trans: "; For(o,0,7) cout<<u[o]<<" "; cout<<endl;
            node v;
            
            for(int k:{0,4}){
                if(u[k]>=1){
                    if(dr[u[k]][u[k+1]][i]>=0){
                        v=u;
                        v[k+0]=v[k+1],v[k+1]=i; upd(v,f[j]);
                    }
                    if(dr[u[k+2]][u[k+3]][i]<=0){
                        v=u;
                        v[k+2]=v[k+3],v[k+3]=i; upd(v,f[j]);
                    }
                    if(dr[u[k+0]][u[k+1]][i]>=0 && dr[u[k+2]][u[k+3]][i]<=0){
                        v=u;
                        v[k+0]=v[k+1]=v[k+2]=v[k+3]=-1; upd(v,f[j]);
                    }
                }
                if(k==4 && u[k]==0){
                    v=u;
                    v[k]=v[k+1]=v[k+2]=v[k+3]=i;
                    upd(v,f[j]);
                }
            }
            f[j]=0;
        }

        For(j,1,tot) f[j]=g[j],g[j]=0;
    }
  //  cerr<<"tot "<<tot<<endl;
    int res=0;
    For(j,1,tot){
      //  For(o,0,7) cout<<(int)sts[j][o]<<" ";cout<<endl;
        if((sts[j][0]==sts[j][1]&&sts[j][1]==sts[j][2]&&sts[j][2]==sts[j][3]) && (sts[j][4]==sts[j][5]&&sts[j][5]==sts[j][6]&&sts[j][6]==sts[j][7])){
        //     cout<<" ok : "<<f[j]<<endl;
            res+=f[j];
        }
    }
    cout<<res*2;
    return 0;
}
/*

5
-22 -1
-12 -20
-5 -18
12 -11
12 -11


4
0 0
0 1
1 0
1 1

2
0 0
1 1
[li,ri]
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 45ms
memory: 396288kb

input:

4
0 0
3 0
0 3
1 1

output:

14

result:

ok "14"

Test #2:

score: 0
Accepted
time: 59ms
memory: 396248kb

input:

8
1 0
2 0
3 1
3 2
2 3
1 3
0 2
0 1

output:

256

result:

ok "256"

Test #3:

score: 0
Accepted
time: 67ms
memory: 396304kb

input:

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

output:

0

result:

ok "0"

Test #4:

score: 0
Accepted
time: 36ms
memory: 321316kb

input:

1
0 0

output:

2

result:

ok "2"

Test #5:

score: 0
Accepted
time: 32ms
memory: 396180kb

input:

2
1000000 0
0 1000000

output:

4

result:

ok "4"

Test #6:

score: 0
Accepted
time: 214ms
memory: 396164kb

input:

40
675677 -903121
254211 732097
792262 -321884
701349 560077
430182 -715346
404091 -587385
-368483 765887
-62363 -93377
964720 739688
-63560 -743279
-445506 491429
758128 486841
571801 -759073
-838475 443367
238435 -29645
651624 -991716
-747006 397530
-616854 -868231
656953 925190
-317709 453131
-16...

output:

0

result:

ok "0"

Test #7:

score: 0
Accepted
time: 212ms
memory: 396308kb

input:

40
-865418 42040
-181476 58360
-864436 597211
-537311 -750515
653760 930646
-79954 431109
507863 569812
-756842 328289
-847028 -653883
-861260 953897
172940 -670358
-897079 -318722
-322040 580667
-110419 -862581
-673197 497171
160617 197820
-685798 -274098
-996233 -444341
-866456 -103514
884216 1302...

output:

0

result:

ok "0"

Test #8:

score: 0
Accepted
time: 224ms
memory: 396272kb

input:

40
-603027 -206745
522738 -843934
-230260 171562
409437 -780802
335077 938627
900036 446118
353133 613669
42034 -253742
897735 244447
162857 -205668
-291578 255993
-400956 -443041
363918 -151931
917921 -153303
-784264 -923508
707263 -65982
320014 -741462
69068 84317
-313477 -222217
398310 -623897
-3...

output:

0

result:

ok "0"

Test #9:

score: 0
Accepted
time: 3008ms
memory: 592304kb

input:

40
304228 474832
339193 698218
532597 847991
301767 487867
301484 489588
312216 636492
301156 589241
864900 341382
815916 788658
902793 401404
383829 322243
311538 634321
934723 542442
934711 543872
849568 323602
317879 652850
297933 558903
545644 229664
426994 283936
932543 577716
803173 282502
612...

output:

1099511627776

result:

ok "1099511627776"

Test #10:

score: 0
Accepted
time: 2964ms
memory: 660424kb

input:

40
682213 413770
732917 632515
533711 341444
717776 670453
678714 725314
288718 555727
299151 498666
677853 726202
293244 521060
297629 503629
596562 779661
718283 465927
729188 643918
327210 694619
679785 724197
316576 458162
538430 793500
462138 788338
725100 654534
394541 375547
713627 457132
416...

output:

1099511627776

result:

ok "1099511627776"

Test #11:

score: 0
Accepted
time: 2870ms
memory: 590172kb

input:

40
690327 796610
899721 492039
415914 773849
868312 633436
551829 173087
893762 432825
426445 779673
625932 175784
710328 788345
880450 384750
454256 196451
318337 302277
540174 814957
255738 469043
894001 434064
698123 195603
526750 176060
829542 695452
343103 716386
326056 292299
771344 752130
450...

output:

1099511627776

result:

ok "1099511627776"

Test #12:

score: 0
Accepted
time: 2777ms
memory: 579288kb

input:

40
810134 763604
960023 517240
378773 299194
478204 770342
490699 777139
880031 704327
874167 270102
835337 234825
871394 713698
449497 229061
322449 426117
607498 811521
759209 191266
831662 748834
837502 744366
318150 527858
878136 274425
321341 431827
596871 810315
622934 812641
961137 489311
537...

output:

1099511627776

result:

ok "1099511627776"

Test #13:

score: 0
Accepted
time: 2481ms
memory: 558696kb

input:

40
396527 348618
490745 618330
623640 452117
516281 613752
569378 586849
400552 597147
481386 324337
556837 595804
536838 336715
510565 328020
381347 583103
622263 499529
336527 429250
342745 530846
462836 618172
351226 547269
341012 526731
621413 503618
624731 463870
585093 370850
353985 391507
463...

output:

1099511627776

result:

ok "1099511627776"

Test #14:

score: 0
Accepted
time: 222ms
memory: 396308kb

input:

40
348806 292250
881310 507145
648771 458522
350121 286404
528525 328171
523147 327950
877205 193023
646317 481228
650172 644274
592950 562001
491602 607700
633484 516916
561404 635604
464750 571606
472301 337351
345667 309392
918763 292245
410964 522730
414282 384403
493502 330811
560614 577972
398...

output:

8

result:

ok "8"

Test #15:

score: 0
Accepted
time: 224ms
memory: 396368kb

input:

40
631147 694274
801330 386943
456054 706286
314819 551910
295549 416690
740272 274040
442799 215826
772440 316962
444723 214527
572571 192378
358037 619847
416386 225356
265566 504075
261670 452652
721008 255313
365569 628014
364724 627132
263927 424837
715004 648254
701465 658663
271455 529405
308...

output:

36864

result:

ok "36864"

Test #16:

score: 0
Accepted
time: 225ms
memory: 396440kb

input:

40
210925 483256
509427 524129
809917 725767
384834 346319
557745 528825
483602 235571
264838 751922
526203 199698
484768 211214
248401 727112
380663 267920
430353 248619
458849 502048
854618 534655
840176 460189
392285 856143
581598 201220
227105 433548
745983 315087
310607 315913
601366 520670
714...

output:

16

result:

ok "16"

Test #17:

score: 0
Accepted
time: 209ms
memory: 396260kb

input:

40
363273 607647
229688 689421
500548 618284
554597 526278
444713 454199
372428 788220
406841 631376
555998 588129
328827 555219
398447 444307
502665 423682
551683 546767
441407 779555
536627 532576
381178 620420
553258 538828
347019 590304
548716 483428
324819 502439
439662 780138
501153 488050
274...

output:

4

result:

ok "4"

Test #18:

score: 0
Accepted
time: 212ms
memory: 396500kb

input:

40
522103 590769
451087 404353
248186 531507
545529 276178
551315 272949
822791 356753
632990 648076
463201 529782
464835 443222
439300 688314
456862 384089
810188 561943
308240 442013
506415 629942
268588 481777
844414 467749
302924 445714
548067 274731
413260 696245
522659 588286
820037 546073
530...

output:

8

result:

ok "8"

Test #19:

score: 0
Accepted
time: 152ms
memory: 396104kb

input:

25
1000000 301342
941216 1000000
1000000 -62296
895781 1000000
581632 -1000000
-1000000 -154194
-1000000 153865
971166 -1000000
-263476 556928
-521153 957989
237370 -200306
420086 506371
726827 306375
254853 350960
868207 207258
676749 -851731
643827 610533
-288759 828217
208999 -720998
-798085 -118...

output:

0

result:

ok "0"

Test #20:

score: 0
Accepted
time: 68ms
memory: 396252kb

input:

10
180999 -838280
154495 -838280
2235 563601
140010 815122
946633 -795985
946633 509711
508876 815122
2235 431578
535888 763223
678578 -684508

output:

480

result:

ok "480"

Test #21:

score: 0
Accepted
time: 171ms
memory: 396232kb

input:

30
226145 -291063
542091 -291063
193371 418524
193371 768134
430055 990449
768191 990449
856005 92420
856005 807316
759042 270477
555558 -148619
818436 42086
361829 -123389
599337 136021
429099 698657
786410 508157
693765 -69218
246457 -103398
320849 918555
473533 610258
666957 37529
225422 267423
4...

output:

0

result:

ok "0"

Test #22:

score: 0
Accepted
time: 272ms
memory: 404116kb

input:

40
456921 59061
924694 399983
78069 364879
524788 64328
77742 634094
149582 240046
265094 132245
80314 380466
914963 365190
168771 783999
847946 774257
367365 915664
903553 665872
841508 228345
131534 254001
65610 587110
94829 320782
397916 931117
733832 876305
329861 98227
590889 926741
93399 34156...

output:

461242368

result:

ok "461242368"

Test #23:

score: 0
Accepted
time: 269ms
memory: 399348kb

input:

40
74770 642492
767559 868521
170540 189131
778350 851634
905066 702745
941921 400552
75505 658075
125720 755144
487704 948301
929431 370718
48350 534594
946331 577280
455029 53791
228921 142731
737201 111244
208256 153490
950023 430177
955374 505514
67825 635680
109151 719913
897491 717221
949996 5...

output:

393879552

result:

ok "393879552"

Test #24:

score: 0
Accepted
time: 210ms
memory: 396320kb

input:

40
760944 846397
107392 299082
650096 93117
108045 323216
919513 405710
931324 454806
857526 738864
803955 195874
494920 58997
66353 505811
848900 751296
752670 138521
925074 585996
142577 241624
557757 70178
105808 671739
922428 401827
294457 122332
227421 832539
873862 266041
567116 71539
879012 2...

output:

0

result:

ok "0"

Test #25:

score: 0
Accepted
time: 212ms
memory: 396420kb

input:

40
302273 899216
838712 210614
41024 522460
130799 226406
718640 117213
41535 531200
885700 713460
310809 903332
254292 133999
79910 686246
885343 714103
936862 642532
270418 123673
927508 668526
60427 466749
345815 87015
667680 87262
756151 118490
126634 734366
939416 426631
552805 937654
65484 598...

output:

995328

result:

ok "995328"

Test #26:

score: 0
Accepted
time: 224ms
memory: 396372kb

input:

40
830104 813282
875052 743100
674776 920200
949435 428429
44903 500977
61860 376922
195925 838605
724611 886409
148825 755192
752873 852848
117338 295021
268399 882260
265374 134764
46799 458482
775396 835565
934312 605522
439306 48967
514442 66136
314077 892275
945573 407376
741003 123597
71590 62...

output:

0

result:

ok "0"

Test #27:

score: 0
Accepted
time: 555ms
memory: 428212kb

input:

38
500000 500000
409915 362927
561914 348109
362458 410633
645690 575357
663823 491854
544591 657848
462812 659754
411454 638072
586382 639436
384593 616557
336022 496048
336474 512793
629009 398704
634588 406243
607644 376238
595740 366815
648081 429457
660159 535403
352066 570851
536330 340049
592...

output:

43876354

result:

ok "43876354"

Test #28:

score: 0
Accepted
time: 590ms
memory: 427028kb

input:

40
500000 500000
481269 389003
542665 395833
424404 416595
611476 515634
569150 411177
418542 422310
559346 595652
418401 422458
459919 394811
575375 583605
447504 400424
573582 414813
526868 609313
511657 611961
434232 408645
391424 470293
392761 534220
490165 387864
503143 612523
596787 442525
426...

output:

1220116482

result:

ok "1220116482"

Test #29:

score: 0
Accepted
time: 603ms
memory: 430620kb

input:

39
500000 500000
514718 546515
541997 475169
517618 454504
548073 491677
455507 479984
542414 475889
482359 454513
458200 474840
525597 541534
468412 462818
506675 451670
508255 451915
463822 467267
507814 451841
529746 538672
492423 451804
535439 466469
540486 527224
518376 454804
457009 476934
459...

output:

370421762

result:

ok "370421762"

Test #30:

score: 0
Accepted
time: 369ms
memory: 415264kb

input:

32
500000 500000
296838 387667
425870 280003
695826 375316
732146 498591
268962 522700
290614 600257
577809 281277
281115 577351
279285 428036
732021 492246
279243 571834
680973 354595
634356 310680
657721 670346
713944 590120
502312 267861
729158 537154
449221 273471
354083 319439
268851 521543
283...

output:

14117890

result:

ok "14117890"

Test #31:

score: 0
Accepted
time: 594ms
memory: 425828kb

input:

38
500000 500000
502318 361210
374595 440488
362496 518995
437837 624112
367956 457193
489452 638408
411930 607293
516709 637800
528304 635893
446035 372110
377797 565837
553776 627970
383811 424052
456430 368206
362418 518420
464432 365825
614053 579120
413931 608904
606093 589511
601089 404874
429...

output:

279334914

result:

ok "279334914"

Test #32:

score: 0
Accepted
time: 2488ms
memory: 729620kb

input:

33
-304 277248
-140 58800
-533 852267
450 607500
226 153228
-196 115248
-518 804972
-300 270000
-328 322752
-362 393132
469 659883
537 865107
387 449307
-190 108300
565 957675
-201 121203
187 104907
-26 2028
63 11907
275 226875
77 17787
248 184512
225 151875
-192 110592
78 18252
-486 708588
-163 797...

output:

8589934592

result:

ok "8589934592"

Test #33:

score: -100
Time Limit Exceeded

input:

38
329 108241
180 32400
484 234256
67 4489
-202 40804
-516 266256
274 75076
-282 79524
-309 95481
890 792100
-904 817216
840 705600
-523 273529
-11 121
571 326041
-786 617796
620 384400
370 136900
-609 370881
599 358801
687 471969
-790 624100
825 680625
235 55225
85 7225
-39 1521
834 695556
717 5140...

output:


result: