原题地址: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=Y2−Y1
B
=
X
1
−
X
2
B = X_1 - X_2
B=X1−X2
C
=
X
2
∗
Y
1
−
X
1
∗
Y
2
C = X_2*Y_1 - X_1*Y_2
C=X2∗Y1−X1∗Y2
所以,对于一条直线使用一个
p
a
i
r
<
A
,
B
pair<A,B
pair<A,B>和
C
C
C来表示.
我们统计出所有不同的斜率,那么假设斜率为
A
A
A的有
a
a
a条,斜率为
B
B
B的有
b
b
b条,那么就会产生
a
∗
b
a*b
a∗b个交点.
这样逐一统计即可.
注意:要处理三点共线的情况,这也是为什么下面的代码使用
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内容请搜索靠谱客的其他文章。
发表评论 取消回复