我是靠谱客的博主 个性书包,这篇文章主要介绍Codeforces Round #558 (Div. 2) C.Power Transmission,现在分享给大家,希望可以做个参考。

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

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

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

A = Y 2 − Y 1 A = Y_2 - Y_1 A=Y2Y1
B = X 1 − X 2 B = X_1 - X_2 B=X1X2
C = X 2 ∗ Y 1 − X 1 ∗ Y 2 C = X_2*Y_1 - X_1*Y_2 C=X2Y1X1Y2
所以,对于一条直线使用一个 p a i r &lt; A , B pair&lt;A,B pair<A,B>和 C C C来表示.
我们统计出所有不同的斜率,那么假设斜率为 A A A的有 a a a条,斜率为 B B B的有 b b b条,那么就会产生 a ∗ b a*b ab个交点.
这样逐一统计即可.
注意:要处理三点共线的情况,这也是为什么下面的代码使用 s e t set 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内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(64)

评论列表共有 0 条评论

立即
投稿
返回
顶部