思路

首先可以发现转化，答案也就等于每个

i

与

j

的组合再减去平行的个数。即

\frac{n \times (n-1)}{2}

减去两条线相平行的个数。

接下来我们需要考虑如何去求这个东西。通过对样例解释的观察与一些手玩，可以发现

a_i

，

b_i

与

a_{i} + k

，

b_{i}-k

是平行的。

k

是指一个能使上式大于 0 小于等于

n

的整数，可正可负。注意

k

不等于 0。

这就结束了吗？并没有。例如，如果

a_{i} + k

是大于

n

的，这并不代表它不成立。在一个环上，物极必反（感性理解一下）。到

n

后会跳到 1。所以

a_{i} + k

将会变成

a_{i} + k - n

。

好麻烦！这不仅需要经过大量分讨，并且也没法在时间限制下实现。

进一步观察上式，如果从两对点的和入手，事情是不是就无比简单了？只有两种情况，两对点的和相等或差

n

。

开一个 map，每次将

a_i + b_i

在 map 内加一下就行了。答案也很好求（详见代码）。

AC code

CPP

#include<bits/stdc++.h>
using namespace std;
long long n,m,sum;
map<long long,long long>ji;
int main(){
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=m;i++){
        long long a,b;
        scanf("%lld%lld",&a,&b);
        sum+=ji[a+b]+ji[a+b+n]+ji[a+b-n];//真的不会算重！因为边是按顺序加的。
        ji[a+b]++;
    }
    printf("%lld",m*(m-1)/2-sum);
}

AT_abc402_d 题解

文章操作

思路

AC code

相关推荐

评论

AT_abc402_d 题解