QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#814563#9882. Two Convex Setsucup-team3161#Compile Error//C++176.0kb2024-12-14 18:21:192024-12-14 18:21:21

Judging History

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

  • [2024-12-14 18:21:21]
  • 评测
  • [2024-12-14 18:21:19]
  • 提交

answer

// what is matter? never mind. 
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("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];
using u64 = unsigned long long;
#undef int
struct hshMap {
    static const int mod = 19260817;
    struct node {
        unsigned long long key; int val, nxt;
    } a[maxn];
    int cnt, tot, head[mod];
    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*256ll+o[i];
    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;
}

vector<P>convex(vector<P>a){
	int n=a.size(),m=0; if(n<=1)return a;
	sort(a.begin(),a.end());
	vector<P>st(n*2); int tp=0;
	For(i,0,n-1){
		while(tp>1 && cmp3(st[tp-2],st[tp-1],a[i])<=0)--tp;
		st[tp++]=a[i];
	}
	int t=tp;
	Rep(i,n-2,0){
		while(tp>t && cmp3(st[tp-2],st[tp-1],a[i])<=0)--tp;
		st[tp++]=a[i];
	}
	st.resize(tp-1);
	return st;
}

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]);
    }

    vector<P>qwq;
    For(i,1,n)qwq.pb(p[i]);
    qwq=convex(qwq);
    if(qwq.size()==n){
        cout<<(1ll<<n)<<endl;
        exit(0);
    }

    
 //   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

In file included from /usr/include/c++/13/string:43,
                 from /usr/include/c++/13/bitset:52,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:52,
                 from answer.code:5:
/usr/include/c++/13/bits/allocator.h: In destructor ‘std::_Vector_base<P, std::allocator<P> >::_Vector_impl::~_Vector_impl()’:
/usr/include/c++/13/bits/allocator.h:184:7: error: inlining failed in call to ‘always_inline’ ‘std::allocator< <template-parameter-1-1> >::~allocator() noexcept [with _Tp = P]’: target specific option mismatch
  184 |       ~allocator() _GLIBCXX_NOTHROW { }
      |       ^
In file included from /usr/include/c++/13/vector:66,
                 from /usr/include/c++/13/functional:64,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:53:
/usr/include/c++/13/bits/stl_vector.h:133:14: note: called from here
  133 |       struct _Vector_impl
      |              ^~~~~~~~~~~~