QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#814494 | #9882. Two Convex Sets | ucup-team3161# | TL | 3963ms | 525244kb | C++17 | 5.4kb | 2024-12-14 17:53:48 | 2024-12-14 17:53:48 |
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 20000005
#define inf 0x3f3f3f3f3f3f3f3f
int n;
P p[maxn];
int dr[45][45][45];
#undef int
struct hshMap {
const int mod = 1111151;
struct node {
ll key; int val, nxt;
} a[maxn];
int cnt, tot, head[1111151];
inline int calc(ll 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: 19ms
memory: 325192kb
input:
4 0 0 3 0 0 3 1 1
output:
14
result:
ok "14"
Test #2:
score: 0
Accepted
time: 36ms
memory: 325248kb
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: 16ms
memory: 325192kb
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: 321076kb
input:
1 0 0
output:
2
result:
ok "2"
Test #5:
score: 0
Accepted
time: 35ms
memory: 325336kb
input:
2 1000000 0 0 1000000
output:
4
result:
ok "4"
Test #6:
score: 0
Accepted
time: 43ms
memory: 325268kb
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: 23ms
memory: 325332kb
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: 37ms
memory: 325348kb
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: 3963ms
memory: 525244kb
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: -100
Time Limit Exceeded
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