有部分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 ",ans[i].x,ans[i].y); } }
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; }
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下去
代码如下
#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 lson l,mid,rt<<1 #define rson mid+1,r,rt<<1|1 #define bug printf("********* ") #define FIN freopen("input.txt","r",stdin); #define FON freopen("output.txt","w+",stdout); #define IO ios::sync_with_stdio(false),cin.tie(0) #define debug1(x) cout<<"["<<#x<<" "<<(x)<<"] " #define debug2(x,y) cout<<"["<<#x<<" "<<(x)<<" "<<#y<<" "<<(y)<<"] " #define debug3(x,y,z) cout<<"["<<#x<<" "<<(x)<<" "<<#y<<" "<<(y)<<" "<<#z<<" "<<z<<"] " const double eps = 1e-8; const int mod = 1000000007; const int maxn = 2e5 + 5; const double pi = acos(-1); const int INF = 0x3f3f3f3f; const LL INFLL = 0x3f3f3f3f3f3f3f3f; struct TREE { int ls, rs, s; LL sum; } T[maxn << 5]; int tot = 0; struct QUERY { int l, r, k; LL ans; } q[maxn << 2]; LL read() { int x = 0, f = 1; char ch = getchar(); while(ch < '0' || ch > '9') { if(ch == '-')f = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); } return x * f; } void push_up(int rt) { int ls = T[rt].ls; int rs = T[rt].rs; T[rt].s = T[ls].s + T[rs].s; T[rt].sum = T[ls].sum + T[rs].sum; return; } void update(int l, int r, int &rt, int pre, int x) { rt = ++tot; T[rt] = T[pre]; if(l == r) { T[rt].s++; T[rt].sum += (x - (x >> 1)); return; } int mid = (l + r) >> 1; if(x <= mid) update(l, mid, T[rt].ls, T[pre].ls, x); else update(mid + 1, r, T[rt].rs, T[pre].rs, x); push_up(rt); } LL query(int l, int r, int rt, int pre, int k) { if(l == r) return (LL)(k * (l - (l >> 1))); int ls = T[rt].ls; int rs = T[rt].rs; int Ls = T[pre].ls; int Rs = T[pre].rs; int mid = (l + r) >> 1; LL ans = 0; if(k > T[rs].s - T[Rs].s) { ans += T[rs].sum - T[Rs].sum; ans += query(l, mid, ls, Ls, k - (T[rs].s - T[Rs].s)) ; } else { ans += query(mid + 1, r, rs, Rs, k); } return ans; } LL sum[maxn]; int root[maxn]; LL a[maxn]; int num[maxn]; int main() { #ifndef ONLINE_JUDGE FIN #endif int n, m; sum[0] = 0; scanf("%d%d", &n, &m); for(int i = 1; i <= n; i++) { a[i] = read(); sum[i] = sum[i - 1] + a[i]; } for(int i = 1; i <= m; i++) { q[i].l = read(); q[i].r = read(); q[i].k = read(); q[i].ans = sum[q[i].r] - sum[--q[i].l]; } for (int i = 29; i >= 0; --i) { int L = 1 << i, R = 2 << i; //二进制分组 tot = 0;//重构 for (int j = 1; j <= n; ++j) { if ((a[j] >> i) & 1) { update(L, R, root[j], root[j - 1], a[j]); sum[j] = sum[j - 1] + a[j] - (a[j] >> 1); num[j] = num[j - 1] + 1; } else { root[j] = root[j - 1]; sum[j] = sum[j - 1]; num[j] = num[j - 1]; } } for (int j = 1; j <= m; ++j) { if (q[j].k && q[j].k >= num[q[j].r] - num[q[j].l]) { q[j].k -= num[q[j].r] - num[q[j].l]; q[j].ans -= sum[q[j].r] - sum[q[j].l]; } else { q[j].ans -= query(L, R, root[q[j].r], root[q[j].l], q[j].k); q[j].k = 0; } } for (int j = 1; j <= n; ++j) if ((a[j] >> i) & 1) a[j] >>= 1; } for(int i = 1; i <= m; i++) { printf("%lld ", q[i].ans); } return 0; }
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(""); } }
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; }
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; }
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("********* ") #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; }
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 ", 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; }