solved.ac class 7++ 도전기 2

작성일 | In

이전 포스트
solved.ac class 7++ 도전기 1

　팀연습셋(NWERC 2020)과 2018년도 ICPC 업솔빙을 끝마쳤으니, 다시 class 7++ 등반으로 돌아왔습니다. 오늘은 class 7 문제중 5개를 골라(마찬가지로 풀이를 떠올린 문제들만 골랐습니다.), 100분 안에 해결하는 것을 목표로 했습니다. 5문제 중 두 문제 풀이가 거의 똑같고, 한 문제는 지난주에 푼 문제랑 거의 똑같아서 지난번보다 문제수가 하나 많음에도 시간을 줄였는데, 결과적으로는 썩 좋지 못한 판단이었던 것 같네요.. 아무튼 문제 목록은 다음과 같습니다.

　A. BOJ 3033 - 가장 긴 문자열
　B. BOJ 3878 - 점 분리
　C. BOJ 11407 - 책 구매하기 3
　D. BOJ 11479 - 서로 다른 부분 문자열의 개수 2
　E. BOJ 18227 - 성대나라의 물탱크

　A. BOJ 3033 - 가장 긴 문자열 (Solved at 18 min)

　티어: 플래티넘 III

　LCP 배열 자체가 suffix array가 주어졌을 때, 사전순으로 바로 뒤에 있는 suffix와 처음 몇 글자가 일치하는지를 나타내기 때문에, LCP 배열의 최댓값을 출력하기만 하면 되는 문제입니다.

　코드 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#define fastio() ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)

using namespace std;

vector<int> getsa(const string& s){
    int len=s.length();
    vector<int> sa(len),rnk(len+1,0),tmp(len),cnt(max(len+1,256),0);
    for(int i=0;i<len;++i){
        rnk[i]=s[i];
        sa[i]=i;
    }
    for(int cl=1;cl<=len;cl<<=1){
        fill(cnt.begin(),cnt.end(),0);
        for(int i=0;i<len;++i)cnt[rnk[min(sa[i]+cl,len)]]++;
        for(int i=1;i<cnt.size();++i)cnt[i]+=cnt[i-1];
        for(int i=len-1;i>=0;--i)tmp[--cnt[rnk[min(sa[i]+cl,len)]]]=sa[i];
        fill(cnt.begin(),cnt.end(),0);
        for(int i=0;i<len;++i)cnt[rnk[sa[i]]]++;
        for(int i=1;i<cnt.size();++i)cnt[i]+=cnt[i-1];
        for(int i=len-1;i>=0;--i)sa[--cnt[rnk[tmp[i]]]]=tmp[i];
        int r=1;
        tmp[sa[0]]=r;
        for(int i=1;i<len;++i){
            if(rnk[sa[i-1]]!=rnk[sa[i]]||rnk[min(sa[i-1]+cl,len)]!=rnk[min(sa[i]+cl,len)])++r;
            tmp[sa[i]]=r;
        }
        for(int i=0;i<len;++i)rnk[i]=tmp[i];
    }
    return sa;
}

vector<int> getlcp(const string s,const vector<int>& sa){
    int len=s.length();
    vector<int> lcp(len),rev(len);
    for(int i=0;i<len;++i)rev[sa[i]]=i;
    for(int i=0,k=0;i<len;++i){
        int idx=rev[i];
        if(!idx){
            lcp[idx]=-1;
            continue;
        }
        for(int j=k;j<len;++j){
            if(sa[idx]+j<len&&sa[idx-1]+j<len&&s[sa[idx]+j]==s[sa[idx-1]+j])++k;
            else break;
        }
        lcp[idx]=k;
        if(k>0)--k;
    }
    return lcp;
}

int main(){
    fastio();
    int n,ans=0;
    string s;
    vector<int> sa,lcp;
    cin>>n>>s;
    sa=getsa(s);
    lcp=getlcp(s,sa);
    for(auto i:lcp)ans=max(ans,i);
    cout<<ans;
}

　D. BOJ 11479 - 서로 다른 부분 문자열의 개수 2 (Solved at 23 min)

　티어: 플래티넘 II

　A번과 마찬가지로 Suffix Array를 사용하는 문제입니다. 우선 i번째 suffix는 문자열의 길이 - i개의 ‘i번째에서 시작하는’ 부분 문자열을 포함하고 있습니다. 이 중에서 다음 suffix와 겹치는(서로 같은) 부분 문자열은 lcp[i]개이므로, 각 suffix에 대해서, lcp[i]개만큼은 제외해주어야 합니다. 이 값을 전체 suffix에 대해서 계산해서 더해주면 이 문제를 해결할 수 있습니다. 다만 문자열 S의 길이가 최대 100만이기 때문에, 시간제한이 좀 빡세네요. 제 Suffix Array 구현은 \( O(N \log N) \)인데도 4초가 걸리는 것으로 보아, \( O(N \log^2 N) \) 구현은 정말 아슬아슬하게 통과하거나, 시간 초과가 날 것으로 보입니다.

　코드 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#define fastio() ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)

using namespace std;
using ll=long long;

vector<int> getsa(const string& s){
    int len=s.length();
    vector<int> sa(len),rnk(len+1,0),tmp(len),cnt(max(len+1,256),0);
    for(int i=0;i<len;++i){
        rnk[i]=s[i];
        sa[i]=i;
    }
    for(int cl=1;cl<=len;cl<<=1){
        fill(cnt.begin(),cnt.end(),0);
        for(int i=0;i<len;++i)cnt[rnk[min(sa[i]+cl,len)]]++;
        for(int i=1;i<cnt.size();++i)cnt[i]+=cnt[i-1];
        for(int i=len-1;i>=0;--i)tmp[--cnt[rnk[min(sa[i]+cl,len)]]]=sa[i];
        fill(cnt.begin(),cnt.end(),0);
        for(int i=0;i<len;++i)cnt[rnk[sa[i]]]++;
        for(int i=1;i<cnt.size();++i)cnt[i]+=cnt[i-1];
        for(int i=len-1;i>=0;--i)sa[--cnt[rnk[tmp[i]]]]=tmp[i];
        int r=1;
        tmp[sa[0]]=r;
        for(int i=1;i<len;++i){
            if(rnk[sa[i-1]]!=rnk[sa[i]]||rnk[min(sa[i-1]+cl,len)]!=rnk[min(sa[i]+cl,len)])++r;
            tmp[sa[i]]=r;
        }
        for(int i=0;i<len;++i)rnk[i]=tmp[i];
    }
    return sa;
}

vector<int> getlcp(const string s,const vector<int>& sa){
    int len=s.length();
    vector<int> lcp(len),rev(len);
    for(int i=0;i<len;++i)rev[sa[i]]=i;
    for(int i=0,k=0;i<len;++i){
        int idx=rev[i];
        if(!idx){
            lcp[idx]=-1;
            continue;
        }
        for(int j=k;j<len;++j){
            if(sa[idx]+j<len&&sa[idx-1]+j<len&&s[sa[idx]+j]==s[sa[idx-1]+j])++k;
            else break;
        }
        lcp[idx]=k;
        if(k>0)--k;
    }
    return lcp;
}

int main(){
    fastio();
    ll ans=0;
    string s;
    vector<int> sa,lcp;
    cin>>s;
    sa=getsa(s);
    lcp=getlcp(s,sa);
    for(int i=0;i<lcp.size();++i){
        if(!i)ans+=s.size()-sa[i];
        else ans+=s.size()-sa[i]-lcp[i];
    }
    cout<<ans;
}

　C. BOJ 11407 - 책 구매하기 3 (Solved at 82 min)

　티어: 플래티넘 II

　결정적으로 이 문제때문에 망했습니다. 팀노트를 따라치는 과정에서 ‘-=’를 ‘=-‘로 잘못 옮겨적어서 디버깅에만 근 1시간을 날렸습니다. 거기다 지난번이랑 똑같은 실수(memset을 memory.h를 include하지 않고 사용)하는 바람에 컴파일 에러도 한번 했네요. 대회때는 #include <bits/stdc++.h>를 사용하기 때문에 치명적인 실수는 아니긴 해도 이런 실수는 좀 줄여야 하는데, 쉽지 않네요..

　별개로 이 문제도 책 구매하기와 동일하게 mcmf 기본문제이기 때문에, 별도의 풀이설명 없이 코드만 첨부하도록 하겠습니다.

　코드 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include<cstdio>
#include<memory.h>
#include<queue>
#include<vector>
#include<algorithm>
#define inf ((int)1e9)
#define S 0
#define BOOK 100
#define T 201
#define N 210

using namespace std;
using pii=pair<int,int>;
struct edge{int pos,cap,rev,cost;};
vector<edge> graph[N];
void clear(){for(int i=0;i<N;++i)graph[i].clear();}
void add_edge(int s,int e,int x,int c){
    graph[s].push_back({e,x,(int)graph[e].size(),c});
    graph[e].push_back({s,0,(int)graph[s].size()-1,-c});
}
int dist[N],pa[N],pe[N];
bool inq[N];
bool spfa(int src,int sink){
    memset(dist,0x3f,sizeof(dist));
    memset(inq,0,sizeof(inq));
    queue<int> q;
    dist[src]=0;
    inq[src]=1;
    q.push(src);
    bool ok=0;
    while(q.size()){
        int x=q.front();
        q.pop();
        if(x==sink)ok=1;
        inq[x]=0;
        for(int i=0;i<graph[x].size();++i){
            edge e=graph[x][i];
            if(e.cap>0&&dist[e.pos]>dist[x]+e.cost){
                dist[e.pos]=dist[x]+e.cost;
                pa[e.pos]=x;
                pe[e.pos]=i;
                if(!inq[e.pos]){
                    inq[e.pos]=1;
                    q.push(e.pos);
                }
            }
        }
    }
    return ok;
}
pii match(int src,int sink){
    int flow=0,ret=0;
    while(spfa(src,sink)){
        int cap=1e9;
        for(int pos=sink;pos!=src;pos=pa[pos]){
            cap=min(cap,graph[pa[pos]][pe[pos]].cap);
        }
        flow+=cap;
        ret+=dist[sink]*cap;
        for(int pos=sink;pos!=src;pos=pa[pos]){
            int rev=graph[pa[pos]][pe[pos]].rev;
            graph[pa[pos]][pe[pos]].cap-=cap;
            graph[pos][rev].cap+=cap;
        }
    }
    return {flow,ret};
}

int c[110][110],d[110][110];

int main(){
    int n,m,tmp;
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;++i){
        scanf("%d",&tmp);
        add_edge(BOOK+i,T,tmp,0);
    }
    for(int i=1;i<=m;++i){
        scanf("%d",&tmp);
        add_edge(S,i,tmp,0);
    }
    for(int i=1;i<=m;++i)for(int j=1;j<=n;++j)scanf("%d",c[i]+j);
    for(int i=1;i<=m;++i)for(int j=1;j<=n;++j)scanf("%d",d[i]+j);
    for(int i=1;i<=m;++i)for(int j=1;j<=n;++j)add_edge(i,BOOK+j,c[i][j],d[i][j]);
    pii ans=match(S,T);
    printf("%d\n%d",ans.first,ans.second);
}

　E. BOJ 18227 - 성대나라의 물탱크 (Not Solved)

　티어: 플래티넘 III

github

　위와 같은 트리가 있고, 1번 정점이 수도(= 루트 정점)라고 생각해봅시다. 4번 정점에 물을 채우는 상황을 생각해 봅시다. 그러면 1번 정점에 1L, 4번 정점에 2L를 채우게 됩니다. 이번에는 5번 정점에 물을 채운다고 생각해 봅시다. 이번에는 1번 정점에 1L, 2번 정점에 2L, 5번 정점에 3L를 채우게 됩니다. 이때 depth가 1인 1번 정점에는 매번 1L씩, depth가 2인 2, 4번 정점에는 2L씩, depth가 3인 5번 정점에는 3L씩 채워진다는 것을 알 수 있습니다.

　여기서 추가로 해볼 수 있는 관찰은, 4번 정점에 물을 채울때, 같이 채워지는 1번 정점은 4번 정점의 조상 정점(부모 또는 부모의 조상)이고, 5번 정점에 채울 때 같이 채워지는 1, 2번 정점 또한 5번 정점의 조상입니다. 반대로 생각하면, 4번 정점은 1번 정점의 subtree에 속해 있고, 5번 정점은 1, 2번 정점의 subtree에 속해 있다고 볼 수 있습니다. 이 두 가지 관찰을 종합해 보면, 2번 쿼리가 들어올 때마다, 해당 정점의 subtree에 1번 쿼리가 행해진 횟수에 해당 정점의 depth를 곱하면 곧 답이 된다는 것을 알 수 있습니다.

　다만, subtree에 1번 쿼리가 행해진 횟수를 naive하게 구하면 \( O(N^2) \)이 되어 시간 초과가 나므로, 오일러 경로 테크닉을 사용하여 세그먼트 트리로 관리해줘야 \( O(N \log N) \)에 문제를 해결할 수 있습니다

　코드 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include<cstdio>
#include<vector>
#include<algorithm>
#define N (1<<18)
#define cur seg[pos]
#define left seg[pos*2]
#define right seg[pos*2+1]

using namespace std;
using ll=long long;

struct Node{
    int s,e,depth;
    vector<int> v;
};

struct Seg{
    int s,e;
    ll val;
};

int cnt;
Node arr[200010];
Seg seg[N<<1];

int dfs(int p,int idx){
    arr[idx].depth=arr[p].depth+1;
    arr[idx].s=arr[idx].e=++cnt;
    for(auto i:arr[idx].v)if(p!=i)arr[idx].e=dfs(idx,i);
    return arr[idx].e;
}

void update(int pos,int idx){
    if(cur.s>idx||idx>cur.e)return;
    if(cur.s==cur.e){
        ++cur.val;
        return;
    }
    update(pos*2,idx);
    update(pos*2+1,idx);
    cur.val=left.val+right.val;
}

ll query(int pos,int s,int e){
    if(cur.s>e||s>cur.e)return 0;
    if(cur.s>=s&&e>=cur.e)return cur.val;
    return query(pos*2,s,e)+query(pos*2+1,s,e);
}

int main(){
    int n,c,s,e,q,a,b;
    scanf("%d %d",&n,&c);
    for(int i=1;i<n;++i){
        scanf("%d %d",&s,&e);
        arr[s].v.push_back(e);
        arr[e].v.push_back(s);
    }
    dfs(0,c);
    for(int pos=N;pos<2*N;++pos)cur.s=cur.e=pos-N+1;
    for(int pos=N-1;pos;--pos)cur.s=left.s,cur.e=right.e;
    for(scanf("%d",&q);q--;){
        scanf("%d %d",&a,&b);
        if(a==1)update(1,arr[b].s);
        else printf("%lld\n",arr[b].depth*query(1,arr[b].s,arr[b].e));
    }
}

　B. BOJ 3878 - 점 분리 (Not Solved)

　티어: 플래티넘 I

　n(또는 m)이 1인지, 2인지, 3 이상인지에 따라 케이스가 갈립니다. 　
　

1. n, m이 둘다 1인 경우

  • 같은 위치에 점이 2개인 경우가 없으므로, 무조건 YES입니다.

2. n이 2, m이 1인 경우(또는 n이 1, m이 2인 경우)

  • 흰(검은) 점이 검은(흰) 점 2개를 잇는 선분에 속한다면 NO, 아니면 YES입니다.

3. n, m이 둘다 2인 경우

  • 흰 점 2개를 잇는 선분과 검은 점 2개를 잇는 선분이 교차한다면 NO, 아니면 YES입니다. 4. n이 3 이상, m이 1인 경우(또는 n이 1, m이 3 이상인 경우)
  • 흰(검은) 점이 검은(흰) 점의 convex hull 내부에 있지만 않다면, YES입니다. 내부에 있는지 여부 판정은, 흰(검은) 점이 \( (x, y) \)에 있다고 했을 때, 해당 점과 \( (x+1, 10001) \)를 연결하는 선분이 검은(흰) 점의 convex hull 상의 선분 중 정확히 한 개와 교차하면 흰(검은) 점이 검은(흰) convex hull 내부에 있으므로 NO, 그 외의 경우 YES를 출력하면 됩니다.
  • 참고로 \( (x+1, 10001) \)를 잡은 이유는, \( (x, y) \)와 \( (x+1, 10001) \)를 잇는 선분이 지나는 정수좌표가 \( (x, y) \)와 \( (x+1, 10001) \)뿐이기 때문에, 다른 선분의 끝부분과 만나서 실제로는 한 번 교차하지만, 두 번 교차한 것으로 취급되는 경우를 방지할 수 있기 때문입니다.

5. n이 3 이상, m이 2인 경우(또는 n이 2, m이 3 이상인 경우)

  • 흰(검은) 점 2개를 잇는 선분이 검은(흰) 점의 convex hull 상의 선분과 교차하는지 여부를 먼저 판정한 뒤, 아무 흰(검은) 점을 잡고 4번 항목과 동일하게 볼록다각형 내부의 점 판정을 하면 됩니다. 선분이 교차하거나, 흰 점이 볼록다강형 내부에 있다면 NO, 그 외의 경우 YES입니다.

6. n, m 모두 3 이상인 경우

  • 흰 점의 convex hull과 검은 점의 convex hull상의 모든 선분 쌍에 대해 교차하는지 여부를 따진 후, 임의의 흰 점과 검은 점의 convex hull에 대해 볼록다각형 내부의 점 판정을, 그리고 임의의 검은 점과 흰 점의 convex hull에 대해서도 동일하게 볼록다각형 내부의 점 판정을 하면 됩니다.

　여기에 추가로, 모든 흰(검은) 점들이 한 직선위에 있어서 다각형을 형성할 수 없는 경우, 흰(검은) 점의 개수를 2개로 취급하고, 양 끝쪽에 있는 점만 춰해주어야 합니다.

　코드 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
#include<cstdio>
#include<vector>
#include<algorithm>

using namespace std;
using pii=pair<int,int>;

struct point{
    int x,y;
    point(pii a):x(a.first),y(a.second){}
    bool operator==(point& other){return x==other.x&&y==other.y;}
    bool operator<(point& other){
        if(x==other.x)return y<other.y;
        return x<other.x;
    }
};

struct line{
    point p1,p2;
    bool operator<(line& other){
        if(p1==other.p1)return p2<other.p2;
        return p1<other.p1;
    }
};

vector<pii> a,b,c,d;

int ccw(point a,point b,point c){
    int det=(b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
    return !det?0:(det>0?1:-1);
}

bool cross(line a,line b){
    int r1,r2;
    if(a.p2<a.p1)swap(a.p1,a.p2);
    if(b.p2<b.p1)swap(b.p1,b.p2);
    if(b<a)swap(a,b);
    r1=ccw(a.p1,a.p2,b.p1),r2=ccw(a.p1,a.p2,b.p2);
    if(r1==r2&&r1)return 0;
    if(r1==r2){
        if(a.p1.x!=a.p2.x){
            if(a.p2.x<b.p1.x)return 0;
        }
        else if(a.p2.y<b.p1.y)return 0;
        return 1;
    }
    r1=ccw(b.p1,b.p2,a.p1),r2=ccw(b.p1,b.p2,a.p2);
    if(r1==r2&&r1)return 0;
    return 1;
}

bool cmpa(const pii& x,const pii& y){
    int val=ccw(a[0],x,y);
    if(!val)return x<y;
    return val>0;
}

bool cmpb(const pii& x,const pii& y){
    int val=ccw(b[0],x,y);
    if(!val)return x<y;
    return val>0;
}

int main(){
    int t,n,m,x,y,cnt;
    for(scanf("%d",&t);t--;){
        a.clear();
        b.clear();
        c.clear();
        d.clear();
        scanf("%d %d",&n,&m);
        cnt=0;
        for(int i=0;i<n;++i){
            scanf("%d %d",&x,&y);
            a.push_back({x,y});
        }
        for(int i=0;i<m;++i){
            scanf("%d %d",&x,&y);
            b.push_back({x,y});
        }
        if(n==1&&m==1){
            printf("YES\n");
            continue;
        }
        sort(a.begin(),a.end());
        sort(b.begin(),b.end());
        bool flaga=false,flagb=false;
        for(int i=2;i<a.size();++i){
            if(ccw(a[i-2],a[i-1],a[i])){
                flaga=true;
                break;
            }
        }
        if(n>2&&!flaga){
            pii p1=a[0],p2=a[a.size()-1];
            n=2;a.clear();
            a.push_back(p1);a.push_back(p2);
        }
        for(int i=2;i<b.size();++i){
            if(ccw(b[i-2],b[i-1],b[i])){
                flagb=true;
                break;
            }
        }
        if(m>2&&!flagb){
            pii p1=b[0],p2=b[b.size()-1];
            m=2;b.clear();
            b.push_back(p1);b.push_back(p2);
        }
        if(n==1||(n==2&&n<m))swap(n,m),swap(a,b);
        sort(a.begin()+1,a.end(),cmpa);
        sort(b.begin()+1,b.end(),cmpb);
        if(n==2&&m==1){
            if(!ccw(a[0],a[1],b[0])&&a[0]<=b[0]&&b[0]<=a[1])printf("NO\n");
            else printf("YES\n");
            continue;
        }
        if(n==2&&m==2){
            if(cross({a[0],a[1]},{b[0],b[1]}))printf("NO\n");
            else printf("YES\n");
            continue;
        }
        c.push_back(a[0]);
        c.push_back(a[1]);
        for(int i=2;i<n;++i){
            while(c.size()>2&&ccw(c[c.size()-2],c[c.size()-1],a[i])<=0)c.pop_back();
            c.push_back(a[i]);
        }
        if(m!=1){
            d.push_back(b[0]);
            d.push_back(b[1]);
            for(int i=2;i<m;++i){
                while(d.size()>2&&ccw(d[d.size()-2],d[d.size()-1],b[i])<=0)d.pop_back();
                d.push_back(b[i]);
            }
        }
        else d.push_back(b[0]);
        if(m!=1){
            for(int i=0;i<c.size();++i){
                for(int j=0;j<d.size();++j){
                    f(cross({c[i],c[(i+1)%c.size()]},{d[j],d[(j+1)%d.size()]}))++cnt;
                }
            }
            if(cnt){
                printf("NO\n");
                continue;
            }
        }
        cnt=0;
        for(int i=0;i<c.size();++i){
            if(cross({c[i],c[(i+1)%c.size()]},{d[0],pii{d[0].first+1,10001}}))++cnt;
        }
        if(cnt==1){
            printf("NO\n");
            continue;
        }
        if(m<3){
            printf("YES\n");
            continue;
        }
        cnt=0;
        for(int i=0;i<d.size();++i){
            if(cross({d[i],d[(i+1)%d.size()]},{c[0],pii{c[0].first+1,10001}}))++cnt;
        }
        if(cnt==1)printf("NO\n");
        else printf("YES\n");
    }
}