求助,能过样例和hack,但WA0pts

P4557 [JSOI2018] 战争

新的修改: ```cpp #include<bits/stdc++.h> #define reg register #define int long long #define maxn 200100 using namespace std; int n,m,q,cnt1,cnt2,tot; class a_spot { public: a_spot* belong; int x,y; bool operator<(a_spot a) const; a_spot operator-(a_spot a)const; a_spot operator+(a_spot a)const; int operator*(a_spot a)const; void operator=(a_spot a); int len() const {return x*x+y*y;} }a[maxn],b[maxn],C1[maxn],C2[maxn],A[maxn],F[maxn],w; //inline double dis(a_spot p1,a_spot p2){return sqrt((p2.y-p1.y)*(p2.y-p1.y)+(p2.x-p1.x)*(p2.x-p1.x));} //inline double check(a_spot a1,a_spot a2,a_spot b1,a_spot b2){return (a2.x-a1.x)*(b2.y-b1.y)-(b2.x-b1.x)*(a2.y-a1.y);} inline int check(a_spot a,a_spot b,a_spot s){return (a-s)*(b-s);} //bool cmp2(const a_spot&A,const a_spot&B) {return A*B>0||(A*B==0&&A.len()<B.len());} //the postive value means b1->b2 is on a1->a2's left bool a_spot::operator<(a_spot a) const { int t=check(*this,a,belong[1]); if(t>0)return 1; if(t==0&&(*this-belong[0]).len()<(a-belong[0]).len())return 1; return 0; } // a_spot a_spot::operator-(a_spot a)const{return (a_spot){this->belong,this->x-a.x,this->y-a.y};} a_spot a_spot::operator+(a_spot a)const{return (a_spot){0,this->x+a.x,this->y+a.y};} int a_spot::operator*(a_spot a)const{return this->x*a.y-this->y*a.x;} void a_spot::operator=(a_spot a){this->belong=a.belong;this->x=a.x;this->y=a.y;} void build(a_spot*p,a_spot*s,int &n)//build a convex from p {//save the convex in s int cnt=1; for(reg int i=1;i<=n;i++){if(i!=1&&(p[i].y==p[1].y?p[i].x<p[1].x:p[i].y<p[1].y))swap(p[1],p[i]);} sort(p+2,p+1+n); s[1]=p[1]; for(reg int i=2;i<=n;i++) { while(cnt>1&&check(s[cnt],p[i],s[cnt-1])<=0)cnt--; //判断前面的会不会被踢走,如果被踢走那么出栈. s[++cnt]=p[i]; } //checking if s_cnt-1->p_i is on s_cnt-1->s_cnt's right equals to checking s_cnt->p_i s[cnt+1]=p[1];//最后一个点回到凸包起点. n=cnt; } void Minkowski() { for(reg int i=1;i<n;i++) a[i]=C1[i+1]-C1[i];a[n]=C1[1]-C1[n]; for(reg int i=1;i<m;i++) b[i]=C2[i+1]-C2[i];b[m]=C2[1]-C2[m]; A[tot=1]=C1[1]+C2[1]; int p1=1,p2=1; while(p1<=n&&p2<=m) ++tot,A[tot]=A[tot-1]+(a[p1]*b[p2]>0?a[p1++]:b[p2++]); while(p1<=n) ++tot,A[tot]=A[tot-1]+a[p1++]; while(p2<=m) ++tot,A[tot]=A[tot-1]+b[p2++]; } int in(a_spot a) { a.belong=F; if(a*F[1]>0||F[tot]*a>0) return 0; int ps=lower_bound(F+1,F+tot+1,a)-F-1; return (a-F[ps])*(F[ps+1]-F[ps])<=0; } signed main() { scanf("%lld%lld%lld",&n,&m,&q); for(reg int i=1;i<=n;i++) { scanf("%lld%lld",&a[i].x,&a[i].y); a[i].belong=a; } for(reg int i=1;i<=m;i++) { scanf("%lld%lld",&b[i].x,&b[i].y); b[i].belong=b;b[i].x=-b[i].x;b[i].y=-b[i].y; } build(a,C1,n); build(b,C2,m); Minkowski(); for(reg int i=1;i<=tot;i++)A[i].belong=A; build(A,F,tot); for(reg int i=1;i<=n;i++)F[i].belong=F; w=F[1]; for(reg int i=tot;i>=1;i--) F[i]=F[i]-F[1]; sort(F+2,F+tot+1); while(q--) { scanf("%lld%lld",&F[0].x,&F[0].y); printf("%lld\n",in(F[0]-w)); } return 0; } ```
by an_ancient_ghoul @ 2023-07-24 11:57:39


orz
by Meatherm_Follower @ 2023-07-24 13:10:33


@[tanhaotian](/user/555900) 别膜,还没AC,看码
by an_ancient_ghoul @ 2023-07-24 20:58:54


|