大概:给n个点 每两点都有连线 求线段相交的次数
相交斜率一定不同 (斜率相同的条数)*(其他的) 就是于其他相交的次数 总数就/2
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 int gcd(int a, int b) { 5 return !b ? a : gcd(b, a % b); 6 } 7 8 int n, x[1005], y[1005]; 9 10 struct line { 11 int a, b, c; 12 line(int x = 0, int y = 0, int z = 0) { 13 int g = gcd(gcd(x, y), z); 14 a = x / g, b = y / g, c = z / g; 15 } 16 }; 17 vector<line> vl; 18 bool operator<(const line &a, const line &b) { 19 if (a.a != b.a) 20 return a.a < b.a; 21 if (a.b != b.b) 22 return a.b < b.b; 23 if (a.c != b.c) 24 return a.c < b.c; 25 return false; 26 } 27 bool operator==(const line &a, const line &b) { 28 return a.a == b.a && a.b == b.b && a.c == b.c; 29 } 30 map<line, int> sz; 31 32 int main() { 33 scanf("%d", &n); 34 for (int i = 1; i <= n; ++i) 35 scanf("%d%d", x + i, y + i); 36 for (int i = 1; i < n; ++i) 37 for (int j = i + 1; j <= n; ++j) 38 vl.emplace_back(y[i] - y[j], x[j] - x[i], x[i] * y[j] - x[j] * y[i]); 39 sort(vl.begin(), vl.end()); 40 vl.erase(unique(vl.begin(), vl.end()), vl.end()); 41 int tot = vl.size(); 42 for (const line &p : vl) 43 ++sz[line(p.a, p.b, 0)]; 44 long long ans = 0; 45 for (const auto &p : sz) 46 ans += 1LL * p.second * (tot - p.second); 47 printf("%lld ", ans / 2); 48 return 0; 49 }