QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#814527 | #9882. Two Convex Sets | ucup-team3161# | TL | 3479ms | 570356kb | C++17 | 5.5kb | 2024-12-14 18:02:22 | 2024-12-14 18:02:23 |
Judging History
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 10000005
#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: 20ms
memory: 239888kb
input:
4 0 0 3 0 0 3 1 1
output:
14
result:
ok "14"
Test #2:
score: 0
Accepted
time: 44ms
memory: 239964kb
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: 59ms
memory: 239928kb
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: 3ms
memory: 165116kb
input:
1 0 0
output:
2
result:
ok "2"
Test #5:
score: 0
Accepted
time: 20ms
memory: 239900kb
input:
2 1000000 0 0 1000000
output:
4
result:
ok "4"
Test #6:
score: 0
Accepted
time: 235ms
memory: 240024kb
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: 240ms
memory: 240008kb
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: 233ms
memory: 240088kb
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: 3461ms
memory: 433104kb
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: 3479ms
memory: 506436kb
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: 3336ms
memory: 429720kb
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: 3251ms
memory: 417536kb
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: 2936ms
memory: 397732kb
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: 229ms
memory: 240076kb
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: 255ms
memory: 242140kb
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: 217ms
memory: 240212kb
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: 217ms
memory: 239912kb
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: 250ms
memory: 240168kb
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: 141ms
memory: 239988kb
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: 56ms
memory: 239976kb
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: 178ms
memory: 239948kb
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: 277ms
memory: 248080kb
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: 268ms
memory: 244852kb
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: 245ms
memory: 240104kb
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: 225ms
memory: 242284kb
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: 241ms
memory: 240020kb
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: 596ms
memory: 273300kb
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: 621ms
memory: 268916kb
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: 649ms
memory: 273868kb
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: 415ms
memory: 258420kb
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: 646ms
memory: 269088kb
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: 2722ms
memory: 570356kb
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...