### 概念

$$A+B=\{a+b \ | \ a \in A,b \in B \}$$

$$A-B=\{c \ | \ c +B \subseteq A\}$$

### 例题

#### Nagisa

##### Solutiuon
#include <bits/stdc++.h>
#define min(a,b) (a<b?a:b)
#define mid ((l+r+1)>>1)
#define inf LLONG_MAX
#define ll long long
#define maxn 3001000
int x=0,flag=1;char ch=getchar();
while(!isdigit(ch)&&ch!='-') ch=getchar();
if (ch=='-') flag=-1,ch=getchar();
while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch-'0'),ch=getchar();
return x*flag;
}
struct Node{
int x,y;
Node operator + (const Node &b) const{
return (Node){x+b.x,y+b.y};
}
Node operator - (const Node &b) const{
return (Node){x-b.x,y-b.y};
}
ll operator * (const Node &b) const{
return (ll)x*b.y-(ll)y*b.x;
}
bool operator < (const Node &b) const{
int k1=(x<0||(!x&&y<0)),
k2=(b.x<0||(!b.x&&b.y<0));
return k1==k2?*this*b<0:k1<k2;
}
}v[maxn],P1[maxn],P2[maxn],la,F,d;
int n,X,Y,dx,dy,cnt,g1,g2,L1,L2,R1,R2;
void chkmin(int &x,int y){x=x<y?x:y;}
bool find(){
if (d.x<0||d.x>P1[g1].x) return 0;
if (!d.x) return P2[L2].y<=d.y&&d.y<=P1[L1].y;
if (d.x==P1[g1].x) return P2[R2].y<=d.y&&d.y<=P1[R1].y;
int l=1,r=g1;
while(l<r)
if (P1[mid].x>d.x) r=mid-1;
else l=mid;
bool p1=(d-P1[l])*(P1[l+1]-P1[l])>=0;
if (!p1) return 0;
l=1,r=g2;
while(l<r)
if (P2[mid].x>d.x) r=mid-1;
else l=mid;
return (d-P2[l])*(P2[l+1]-P2[l])<=0;
}
void make(){
for (int i=2;i<=n;++i)
v[++cnt]=la-d,la=d,
chkmin(X,d.x),chkmin(Y,d.y);
v[++cnt]=la-F;dx+=X,dy+=Y;
}
void solve(){
X=dx,Y=dy;
std::sort(v+1,v+1+cnt);
P1[g1=1]=Node(0,0);
int top=1,y=0;
for (;top<=cnt;++top){
if (v[top].x<0) break;
++g1;P1[g1]=P1[g1-1]+v[top],y=min(y,P1[g1].y);
}
P2[g2=1]=P1[g1];
for (;top<=cnt;++top)
++g2,P2[g2]=P2[g2-1]+v[top],y=min(y,P2[g2].y);
Y-=y;
for (int i=1;i<<1<=g2;++i) std::swap(P2[i],P2[g2+1-i]);
for (L1=1;P1[L1+1].x==P1[L1].x;++L1);
for (L1=1;P2[L2+1].x==P2[L2].x;++L2);
for (R1=g1;P1[R1-1].x==P1[R1].x;--R1);
for (R2=g2;P2[R2-1].x==P2[R2].x;--R2);
}
int main(){
make(),make(),make();
solve();
}