QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#814494#9882. Two Convex Setsucup-team3161#TL 3963ms525244kbC++175.4kb2024-12-14 17:53:482024-12-14 17:53:48

Judging History

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

  • [2024-12-14 17:53:48]
  • 评测
  • 测评结果:TL
  • 用时:3963ms
  • 内存:525244kb
  • [2024-12-14 17:53:48]
  • 提交

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

result: