CCPC-Winter Camp div2 day5

DIV2

有部分div1的题会写

div1的大佬真的太强了

向他们学习

（好像和zqc大佬说过话了hhh，zqc大佬真的是一个超有意思的人啊，羡慕有妹子队友的zqc大佬）

A：

你有一棵树，你想把它画在平面上，使得没有边相交。

题解：dfs（u，dep）表示我在第dep层，第cnt[dep]列来放置第u个节点

代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;
int n,m;
struct EDGE{
    int v,nxt;
}edge[maxn];
int head[maxn];
int tot=0;
void add_edge(int u,int v){
    edge[tot].v=v;
    edge[tot].nxt=head[u];
    head[u]=tot++;
}
int cnt[maxn];
int vis[maxn];
struct node{
    int x,y;
}ans[maxn];

void dfs(int u,int dep){
    for(int i=head[u];i!=-1;i=edge[i].nxt){
        int v=edge[i].v;
        if(!vis[v]){
            vis[v]=1;
            ans[v].x=dep;
            ans[v].y=cnt[dep];
            cnt[dep]++;
            dfs(v,dep-1);
        }
    }
}
int main(){

    memset(head,-1,sizeof(head));
    tot=0;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        add_edge(u,v);
        add_edge(v,u);
    }
    for(int i=1;i<=n;i++){
        cnt[i]=1;
        vis[i]=0;
    }
    dfs(1,n);
    for(int i=1;i<=n;i++){
        printf("%d %d\n",ans[i].x,ans[i].y);
    }
}

View Code

 

B:

所有n个节点有标号的无根树，直径为0,1,…,n−1的树有多少个。

由于答案很大，对mod取模。

学了一点新知识：purfer序列又和其他神奇的序列一样，我都不会QAQ（晚风为什么这么凉，教练我想学数学

 purfer序列是用来对无根数计数的 ，（大概是无根树的同构balabala的太多了，然后某神奇的科学家就给整出这个序列了）

日后补这个知识点（flag立下了

 

C：

你有一个数列​。你可以进行这样的一次操作，每次选择数列中其中一个数然后将其除2下取整。请问对这些数字进行不超过kk次操作，这些数字的总和最小值可能是多少。’

div2的n只有1e3，虽然说k是1e9，但是非常显然对于每一个ai都最多操作30次即可，复杂度是30*nlogn

代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
int a[maxn];
priority_queue<int> q;
int n, k;
int main() {
    scanf("%d%d", &n, &k);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        q.push(a[i]);
    }
    while(k--) {
        if(q.top() / 2 == 0) break;
        int x = q.top();
        q.pop();
        q.push(x / 2);
    }
    long long ans = 0;
    while(!q.empty()) {
        ans += q.top();
        q.pop();
    }
    cout << ans << endl;
}

View Code

div1的版本有点难，最主要的是他是询问这个区间内进行k 次操作后最小的区间和

这些天camp学到一个知识点叫做拆分，就是把一个数用二进制分组的形式表示，这样一个数最多就可以被表示成log（ai）个数，我们预处理出这n个数拆出来的数，即n*log(n)个数，用主席数维护区间前k大数，所以每次询问得到这个区间前k大和，用区间和减去即可得到k次操作后最小的区间和

但是！！！重点来了，我们计算一下空间复杂度。n*log(a[i])*log(segma(log(a[i])))，被256M卡成弟弟的空间复杂度，所以你没了

不过可爱的dls小姐姐告诉我们，

emmm貌似是用重构主席树，然后离线操作，这样复杂度就被滚了一个log下去，，，，代码调bug中，先留坑

D：

你有一个n*n的矩阵，一开始都是空的，你要在其中填入1到n−2的数字和字符X。

要求每行每列中1到n-2中的每个数都恰好出现了一次，并且恰好有两个字符X。

同时对于第i行，要求两个X之间的数字之和为ri，第i列，要求两个X之间的数字之和为ci​。

 n小于7

大搜索，把所有情况搜出来即可

剪枝1：由于每行每列的和是有限制的，我们维护一个第i行的和sum1和第j列的和sun2，如果sum1、sum2大于这个限制，直接return 即可，（要考虑X是否放了两个的情况）

剪枝2：预处理出加到每行的和可以用哪些数得到，还有每列的和可以用哪些数得到，然后用这些数去枚举暴力，就可以跑出答案（听说dls0ms过了，神仙）

自己没有补（flag++）

队友代码：

#include<bits/stdc++.h>
#define fi first
#define se second
#define iis std::ios::sync_with_stdio(false)
#define pb push_back
#define o2(x) (x)*(x)
using namespace std;
typedef long long LL;
typedef pair<int, LL> pii;
const int  MXN = 2e6 + 6;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
int n;
int vis[15][15];
int visr[15][15];
int visc[15][15];
int needr[15];
int needc[15];
int nowrx[15],nowcx[15];// di  i 行 第一个x的纵坐标  竖 横坐标
int haverx[15],havecx[15];
int nowc[15],nowr[15];
int totc[15],totr[15];
int flag = 0;
int sum;
bool check() {
    for(int i=1; i<=n; i++) {
        if(havecx[i]!=2 || haverx[i]!=2) {
            return 0;
        }
    }
    return 1;
}
void dfs(int x,int y) {
    //cout<<"now:"<<x<<","<<y<<",,"<<flag<<endl;
    if(haverx[x]==0 && sum-totr[x]<needr[x]) return;
    if(havecx[y]==0 && sum-totc[y]<needc[y]) return;
    if(flag ) return ;
    if(x==n+1) {
        if(check())
            flag = 1;
        //cout<<"haha:"<<flag<<endl;
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=n; j++) {
                if(vis[i][j]!=-1) {
                    printf("%d",vis[i][j]);
                } else {
                    printf("X");
                }
            }
            puts("");
        }
        return ;
    }
//    for(int i=1; i<=n; i++) {
//        for(int j=1; j<=n; j++) {
//            if(vis[i][j]!=-1) {
//                printf("%d",vis[i][j]);
//            } else {
//                printf("X");
//            }
//        }
//        puts("");
//    }
    // 判断是否可放x
    if(haverx[x]==0 &&havecx[y]==0) {
        nowrx[x]=y;
        nowcx[y]=x;
        havecx[y]++;
        haverx[x]++;
        vis[x][y]=-1;
        if(y+1>n) {
            if(haverx[x]==2)
                dfs(x+1,1);
        } else {
            dfs(x,y+1);
        }
        vis[x][y]=0;
        nowrx[x]=0;
        nowcx[y]=0;
        havecx[y]--;
        haverx[x]--;
    }
    // 横有了一个x 竖没有x
    else if(haverx[x]==1 && havecx[y]==0) {
        int cnt = nowr[x];//getnum(nowrx[x],y,x,1);
        //cout<<"cnt:"<<cnt<<endl;
        // 第 i 行 两个x之间的属的和满足ri
        if(cnt==needr[x]) {
            havecx[y]++;
            haverx[x]++;
            nowcx[y]=x;
            vis[x][y]=-1;
            if(y+1>n) {
                if(haverx[x]==2)
                    dfs(x+1,1);
            } else {
                dfs(x,y+1);
            }
            vis[x][y]=0;
            havecx[y]--;
            haverx[x]--;
            nowcx[y]=0;
        }
    }
    // 竖有了一个x 横没有x
    else if(haverx[x]==0 && havecx[y]==1) {
        int cnt = nowc[y];//getnum(nowcx[y],x,y,0);
        // 第 i 行 两个x之间的属的和满足ri
        if(cnt==needc[y]) {
            havecx[y]++;
            haverx[x]++;
            nowrx[x]=y;
            vis[x][y]=-1;
            if(y+1>n) {
                if(haverx[x]==2)
                    dfs(x+1,1);
            } else {
                dfs(x,y+1);
            }
            vis[x][y]=0;
            havecx[y]--;
            haverx[x]--;
            nowrx[x]=0;
        }
    }// 横竖都有一个
    else {
        int cnt1 = nowr[x];//getnum(nowrx[x],y,x,1);
        int cnt2 = nowc[y];//getnum(nowcx[y],x,y,0);
        if(cnt1 == needr[x] && cnt2 == needc[y]) {
            havecx[y]++;
            haverx[x]++;
            vis[x][y]=-1;
            if(y+1>n) {
                if(haverx[x]==2)
                    dfs(x+1,1);
            } else {
                dfs(x,y+1);
            }
            vis[x][y]=0;
            havecx[y]--;
            haverx[x]--;
        }
    }
    for(int i=1; i<=n-2; i++) {
        int cnt1 = 0;
        if(haverx[x]==1) {
            cnt1 =nowr[x];//getnum(nowrx[x],y,x,1);

            if(cnt1+i>needr[x]) continue;
            //cout<<"cnt1+i:"<<cnt1+i<<"vs"<<needr[x]<<endl;
        }
        int cnt2 = 0;
        if(havecx[y]==1) {
            cnt2 = nowc[y];//getnum(nowcx[y],x,y,0);
            if(cnt2+i>needc[y]) continue;
        }
        if(visc[y][i]==0 && visr[x][i]==0 ) {
            visc[y][i]=1;
            visr[x][i]=1;
            vis[x][y]=i;
            totc[y]+=i;
            totr[x]+=i;
            if(haverx[x]==1) {
                nowr[x]+=i;
            }
            if(havecx[y]==1) {
                nowc[y]+=i;
            }
            if(y+1>n) {
                if(haverx[x]==2)
                    dfs(x+1,1);
            } else {
                dfs(x,y+1);
            }
            if(haverx[x]==1) {
                nowr[x]-=i;
            }
            if(havecx[y]==1) {
                nowc[y]-=i;
            }
            totc[y]-=i;
            totr[x]-=i;
            visc[y][i]=0;
            visr[x][i]=0;
            vis[x][y]=0;
        }
    }
}
void init() {
    flag = 0;
    memset(vis,0,sizeof vis);
    memset(visr,0,sizeof visr);
    memset(visc,0,sizeof visc);
    memset(needr,0,sizeof needr);
    memset(needc,0,sizeof needc);
    memset(nowrx,0,sizeof nowrx);
    memset(nowcx,0,sizeof nowcx);
    memset(haverx,0,sizeof haverx);
    memset(havecx,0,sizeof havecx);
    memset(nowc,0,sizeof nowc);
    memset(nowr,0,sizeof nowr);
    memset(totc,0,sizeof totc);
    memset(totr,0,sizeof totr);
    sum=0;
    for(int i=1; i<=n-2; i++) {
        sum+=i;
    }
//    cout<<sum<<endl;
}
int main() {
    int T;
    scanf("%d",&T);
    while(T--) {

        scanf("%d",&n);
        init();
        for(int i=1; i<=n; i++) {
            scanf("%d",&needr[i]);
        }
        for(int j=1; j<=n; j++) {
            scanf("%d",&needc[j]);
        }
        dfs(1,1);
        if(T)
            puts("");
    }
}

View Code

E：（待补）

F：

n<=15非常明显的状压dp

状压dp计数，定义状态为dp[i][j][k] ，长度为i到最后一个数是j的状态k的排列的数量

枚举时判断一下如果这个数放进去是否符合题目的序列即可

最后的答案就是长度为n的序列结尾数从1~n，状态为（1<<n）-1 时的和

#include<bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
int n;
char str[20];
int dp[16][16][1 << 16]; //长度为i，结尾是j，状态是k
int main() {
    memset(dp, 0, sizeof(dp));
    scanf("%d %s", &n, str + 1);
    for(int i = 1; i <= n; i++) {
        dp[1][i][(1 << i - 1)] = 1;
    }
    for(int i = 1; i < n; i++) {
        for(int j = 1; j <= n; j++) {
            for(int k = 1; k <= n; k++) {
                if(j != k) {
                    int flag = 0;
                    if(((j % k == 0 && j / k == 2) || (k % j == 0 && k / j == 2)) ) {
                        if(str[i] == '1') {
                            flag = 1;
                        }
                    } else {
                        if(str[i] == '0') {
                            flag = 1;
                        }
                    }
                    //cout<<flag<<endl;
                    if(flag) {
                        for(int p = 0; p < (1 << n); p++) {
                            if((p & (1 << k - 1)) == 0) {
                                dp[i + 1][k][p | (1 << k - 1)] = (dp[i + 1][k][p | (1 << k - 1)] + dp[i][j][p]) % mod;
                            }
                        }
                    }
                }
            }
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; i++)
        ans = (ans + dp[n][i][(1 << n) - 1]) % mod;
    cout << ans << endl;
}

View Code

 G：

数论知识，待补（目测不可做）（真的不可做）（不补了告辞）（可以留着祸害学弟）（去py一下标程）

H：

题意：

 

div1是非常不快乐的树链剖分，div2是非常快乐的dfs

 注意建图，因为最多复制m边，那么最多也就只有1e6条边，直接建就行，然后dfs计数，点对之间的距离就是左侧树的大小*右侧树的大小，算贡献

代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 5;
const int mod = 1e9 + 7;
struct EDGE {
    int v, nxt;
} edge[maxn << 2];
int head[maxn];
int tot;
void add_edge(int u, int v) {
    edge[tot].v = v;
    edge[tot].nxt = head[u];
    head[u] = tot++;
}
long long ans = 0;
long long sz[maxn];
int n, m, u, v, a, b;
void dfs(int u, int pre) {
    sz[u] = 1;
    for(int i = head[u]; i != -1; i = edge[i].nxt) {
        int v = edge[i].v;
        if(v == pre) continue;
        dfs(v, u);
        sz[u] += sz[v];ji
        ans = (ans % mod + (long long)sz[v] * (n * m - sz[v]) % mod) % mod;
    }
}
int main() {
    memset(head, -1, sizeof(head));
    tot = 0;
    scanf("%d%d", &n, &m);
    for(int i = 1; i < n; i++) {
        scanf("%d%d", &u, &v);
        for(int j = 0; j < m; j++) {
            add_edge(u + j * n, v + j * n);
            add_edge(v + j * n, u + j * n);
        }
    }
    for(int i = 1; i < m; i++) {
        scanf("%d%d%d%d", &a, &b, &u, &v);
        add_edge(u + (a - 1) * n, v + (b - 1) * n);
        add_edge(v + (b - 1) * n, u + (a - 1) * n);
    }
    dfs(1, 0);
    cout << ans << endl;
}

View Code

 I：

题意：

比赛最后开的这题，口胡了一大半，但是没有写出来，，，码力太差QAQ

实际上真正写还是差一点的

后来可爱的dls讲了之后再加上学长的帮助后终于会写了（感谢帅气的学长（舔狗舔到最后应有尽有

题解：我们注意到x实际上是不变的，那么，我们每个数无论是怎么根据x排序，他的相对位置是不变的，这样我们就可以用前缀和来维护这个区间和

　　　注意大小关系，那么我们定义一个标记，如果这个数字小于等于x，那么这个数所在的位置的标记为0，否则为1，那么我们只需要用线段树维护区间内0和1的个数

　　　每次操作2的时候，我们只需要统计这个区间内0的个数，将区间（l,l+cnt0-1）给直接覆盖为0，剩下的（l+cnt0，r）覆盖为1

　　　每次操作3的时候，我们同理，统计区间内1的个数，然后覆盖即可

　　　每次操作1的时候，我们分别统计区间(1,l-1)（1，r）内0和1的个数，因为每个数字的相对位置是不变的，所以前缀和的相对位置也是不变的，直接减一减就行，具体看代码就懂啦

代码:

#include <set>
#include <map>
#include <deque>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <bitset>
#include <cstdio>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

typedef long long LL;
typedef pair<LL, LL> pLL;
typedef pair<LL, int> pLi;
typedef pair<int, LL> pil;;
typedef pair<int, int> pii;
typedef unsigned long long uLL;

#define bug printf("*********\n")
#define debug(x) cout<<#x"=["<<x<<"]" <<endl
#define FIN freopen("input.txt","r",stdin);
#define IO ios::sync_with_stdio(false),cin.tie(0)
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
const double eps = 1e-8;
const int mod = 1000000007;
const int maxn = 2e5 + 7;
const double pi = acos(-1);
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3fLL;
int sum0[maxn<<2],sum1[maxn<<2],lazy[maxn<<2];
LL a[maxn],q1[maxn],q2[maxn];
int n,m,x;
void push_up(int rt){
    sum0[rt]=sum0[rt<<1]+sum0[rt<<1|1];
    sum1[rt]=sum1[rt<<1]+sum1[rt<<1|1];
    return;
}
void push_down(int rt,int l,int r,int mid){
    if(lazy[rt]==-1) return;
    lazy[rt<<1]=lazy[rt];
    lazy[rt<<1|1]=lazy[rt];
    if(lazy[rt]==0){
        sum0[rt<<1]=(mid-l+1);
        sum0[rt<<1|1]=r-mid;
        sum1[rt<<1]=0;
        sum1[rt<<1|1]=0;
    }else{
        sum0[rt<<1]=0;
        sum0[rt<<1|1]=0;
        sum1[rt<<1]=mid-l+1;
        sum1[rt<<1|1]=r-mid;
    }
    lazy[rt]=-1;
    return;
}
void build(int l,int r,int rt){
    lazy[rt]=-1;
    if(l==r){
        //cout<<a[l]<<endl;
        if(a[l]<=x){
            sum0[rt]=1;
            sum1[rt]=0;
        }else{
            sum1[rt]=1;
            sum0[rt]=0;
        }
        return;
    }
    int mid=(l+r)>>1;
    build(lson);
    build(rson);
    push_up(rt);
}

void update(int L,int R,int flag,int l,int r,int rt){
    if(L>R) return;
    if(L<=l&&r<=R){
        if(flag==0){
            sum0[rt]=r-l+1;
            sum1[rt]=0;
        }else{
            sum1[rt]=r-l+1;     
            sum0[rt]=0;
        }
        lazy[rt]=flag;
        return;
    }
    int mid=(l+r)>>1;
    push_down(rt,l,r,mid);
    if(L<=mid) update(L,R,flag,lson);
    if(R>mid) update(L,R,flag,rson);
    push_up(rt);
}
int query(int L,int R,int flag,int l,int r,int rt){
    if(L>R) return 0;
    if(L<=l&&r<=R){
        if(flag==0){
            // debug(l);debug(r);
            // debug(rt);
            // debug(sum0[rt]);
            return sum0[rt];
        }else{
            return sum1[rt];
        }
    }
    int mid=(l+r)>>1;
    push_down(rt,l,r,mid);
    int ans=0;
    if(L<=mid) ans+=query(L,R,flag,lson);
    if(R>mid) ans+=query(L,R,flag,rson);
    return ans;
}


int main() {
#ifndef ONLINE_JUDGE
    FIN
#endif
    scanf("%d%d%d",&n,&m,&x);
    int tot1=0,tot2=0;
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
        if(a[i]<=x){
            tot1++;
            q1[tot1]=q1[tot1-1]+a[i];
        }else{
            tot2++;
            q2[tot2]=q2[tot2-1]+a[i];
        }
    }
    build(1,n,1);
    while(m--){
        int op,l,r;
        scanf("%d%d%d",&op,&l,&r);
        if(op==1){
            LL ans=0;
            int cnt1=query(1,l-1,0,1,n,1);
            int cnt2=query(1,r,0,1,n,1);
            // debug(cnt1);
            // debug(cnt2);
            ans+=q1[cnt2]-q1[cnt1];
            int cnt3=query(1,l-1,1,1,n,1);
            int cnt4=query(1,r,1,1,n,1);
            ans+=q2[cnt4]-q2[cnt3];
            cout<<ans<<endl;
        }else if(op==2){
            int cnt1=query(l,r,0,1,n,1);
           if(cnt1>0)
            update(l,l+cnt1-1,0,1,n,1);
            update(l+cnt1,r,1,1,n,1);
        }else{
            // debug(l);
            // debug(r);
            int cnt2=query(l,r,1,1,n,1);
            // debug(cnt2);
            if(cnt2>0)
            update(l,l+cnt2-1,1,1,n,1);
            update(l+cnt2,r,0,1,n,1);
        }

    }
    return 0;
}

View Code

 

J：

题解：

只是端点相交不算相交，其余都算，那么上板子搞就行（T字形也算）

#include<bits/stdc++.h>
using namespace std;
#define db double
const int maxn = 1e5 + 5;
const double eps = 1e-9;
inline sign(double a) {
    return a < -eps ? -1 : a > eps;
}
inline int cmp(double a, double b) {
    return sign(a - b);
}
struct P {
    db x, y;
    P() {};
    P(db _x, db _y): x(_x), y(_y) {}
    P operator+(P p) {
        return {x + p.x, y + p.y};
    }
    P operator-(P p) {
        return {x - p.x, y - p.y};
    }
    db dot(P p) {
        return x * p.x + y * p.y;
    }
    db det(P p) {
        return x * p.y - y * p.x;
    }
};
#define cross(p1,p2,p3) ((p2.x-p1.x)*(p3.y-p1.y)-(p3.x-p1.x)*(p2.y-p1.y))
#define cross0p(p1,p2,p3) sign(cross(p1,p2,p3))
bool chkLL(P p1, P p2, P q1, P q2) { //直线平行
    double a1 = cross(q1, q2, p1);
    double a2 = -cross(q1, q2, p2);
    return sign(a1 + a2) != 0;
}
bool intersect(double l1, double r1, double l2, double r2) {
    if(l1 > r1) swap(l1, r1);
    if(l2 > r2) swap(l2, r2);
    return !(cmp(r1, l2) == -1 || cmp(r2, l1) == -1);
}
bool isSS(P p1, P p2, P q1, P q2) {
    return intersect(p1.x, p2.x, q1.x, q2.x) && intersect(p1.y, p2.y, q1.y, q2.y) &&
           cross0p(p1, p2, q1) * cross0p(p1, p2, q2) <= 0 && cross0p(q1, q2, p1)
           * cross0p(q1, q2, p2) <= 0;
}
double rad(P p1, P p2) {
    return atan2(p1.det(p2), p1.dot(p2));
}
bool xielv(P p1, P p2, P q1, P q2) {
    P p = p2 - p1;
    P q = q2 - q1;
    if(q.det(p) == 0 && cmp(rad(p, q), 0) == 0) return 1;
    return 0;
}
struct node {
    int u, v;
} edge[maxn];
int x[maxn];
int y[maxn];
int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= m; i++) {
        scanf("%d%d", &edge[i].u, &edge[i].v);
    }
    for(int i = 1; i <= n; i++) {
        scanf("%d%d", &x[i], &y[i]);
    }
    int cnt = 0;
    for(int i = 1; i <= m; i++) {
        for(int j = i + 1; j <= m; j++) {
            P p1 = P{(double)x[edge[i].u], (double)y[edge[i].u]};
            P p2 = P{(double)x[edge[i].v], (double)y[edge[i].v]};
            P q1 = P{(double)x[edge[j].u], (double) y[edge[j].u]};
            P q2 = P{(double)x[edge[j].v], (double)y[edge[j].v]};
            if(isSS(p1, p2, q1, q2)) {
                if(edge[i].u == edge[j].u || edge[i].u == edge[j].v || edge[i].v == edge[j].u || edge[i].v == edge[j].v) {
                    //printf("%lld %lld %lld %lld %lld %lld %lld %lld\n", p1.x,p1.y,p2.x,p2.y,q1.x,q1.y,q2.x,q2.y);
                    if(edge[i].u == edge[j].u && xielv(p1, p2, q1, q2)) cnt++;
                    if(edge[i].u == edge[j].v && xielv(p1, p2, q2, q1)) cnt++;
                    if(edge[i].v == edge[j].u && xielv(p2, p1, q1, q2)) cnt++;
                    if(edge[i].v == edge[j].v && xielv(p2, p1, q2, q1)) cnt++;
                } else cnt++;
            }
        }
    }
    cout << cnt << endl;
}

View Code