Codeforces Round #558 (Div. 2) C.Power Transmission

原题地址:https://codeforces.com/contest/1163/problem/C2

题意:给出n个点的坐标,每两个点可以形成一条直线,问形成的所有直线中可以有多少个交点.

思路:由于是直线,所以只要任意两条斜率不一样的直线就一定会产生一个交点.所以考虑从斜率上下手.由于斜率有不存在的这种情况,所以方便起见,这里使用一般式来表示一条直线.
$AX+BY+C=0$
其中

$A=Y_2-Y_1$
$B=X_1-X_2$
$C=X_2\ast Y_1-X_1\ast Y_2$
所以,对于一条直线使用一个$pair<A,B$>和$C$来表示.
我们统计出所有不同的斜率,那么假设斜率为$A$的有$a$条,斜率为$B$的有$b$条,那么就会产生$a\ast b$个交点.
这样逐一统计即可.
注意:要处理三点共线的情况,这也是为什么下面的代码使用$set$的原因.

#include <bits/stdc++.h>
#define eps 1e-8
#define INF 0x3f3f3f3f
#define PI acos(-1)
#define lson l,mid,rt<<1
#define rson mid+1,r,(rt<<1)+1
#define CLR(x,y) memset((x),y,sizeof(x))
#define fuck(x) cerr << #x << "=" << x << endl
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int seed = 131;
const int maxn = 1e5 + 5;
const int mod = 1e9 + 7;
int n;
int x[maxn], y[maxn];
/*
AX+By+C=0;
A = Y2 - Y1
B = X1 - X2
C = X2*Y1 - X1*Y2
*/
typedef pair<int, int>pii;
typedef set<ll>S;
map<pii, S>mp; //每一条直线A,B对对应一个C,pair对相等说明平行,C相等说明共线
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d%d", &x[i], &y[i]);
    }
    for (int i = 1; i <= n - 1; i++) {
        for (int j = i + 1; j <= n; j++) {
            int x1 = x[i];
            int x2 = x[j];
            int y1 = y[i];
            int y2 = y[j];
            int A = y2 - y1;
            int B = x1 - x2;
            int C = x2 * y1 - x1 * y2;
            int gcd = __gcd(A, B);
            A /= gcd;
            B /= gcd;
            C /= gcd;
            pii tmp = make_pair(A, B);
            mp[tmp].insert(C);
        }
    }
    ll ans = 0;
    ll sum = 0;
    map<pii, S>::iterator it;
    for (it = mp.begin(); it != mp.end(); it++) {
        ans += (it->second).size() * sum;
        sum += (it->second).size();
    }
    printf("%lldn", ans);
    return 0;
}

最后

以上就是个性书包最近收集整理的关于Codeforces Round #558 (Div. 2) C.Power Transmission的全部内容，更多相关Codeforces内容请搜索靠谱客的其他文章。