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

106 阅读 0 评论 70 点赞

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

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

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

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

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

复制代码

#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;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#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;
}