Codeforces Round #558 (Div. 2) C2. Power Transmission (Hard Edition)

题目链接：http://codeforces.com/contest/1163/problem/C2

题意：现在有$n$个点，每两个点可以形成一条直线，问有多少对直线相交。

解题心得：

$n$条个点最多可以形成$n\ast (n-1)$条直线（三点同线算形成一条直线），$n$的范围是$1000$，$1,000,000$条直线是可以接受的。两条直线不平行必然相交，假设所有直线两两相交，这样直线对数量为$10^{12}$，也是可以接受的。这个题最难的就是处理三（多）点同线的问题，遍历每一个点与其他点形成的直线，如果当前点分别与其他两个点形成的直线斜率相同那么其他两个点形成的直线就会被覆盖掉，这样可以直接二分查找当前点与其他点形成的斜率，如果有相同该覆盖的覆盖就行了。复杂度是$n\ast n\ast logn$。最后将所有的直线按照斜率排序，斜率相同的必然就是平行且不重合的直线。然后用$n\ast (n-1)$减去相关的平行直线多算出的答案就行了。

---

#include <bits/stdc++.h> using namespace std; const int maxn = 1050; const double esp = 1e-9; int n; struct Node { double x, y; }node[maxn]; struct Line{ int a, b;//形成直线的两个端点的标号 double k;//直线的斜率 bool flag;//该直线是否和之间的直线重合 bool operator < (const Line& x) const { if(this->k != x.k) { return this->k < x.k; } else if(this->a != x.a) { return this->a < x.a; } else if(this->b != x.b) { return this->b < x.b; } else if(this->flag != x.flag) { return this->flag < x.flag; } } }; vector <double> ve;//存储去重之后任意两点形成的直线的斜率 set <Line> temp;//记录i到其它所有点之间的形成的直线 set <Line> ::iterator iter; map <pair<int,int>, int> maps;//标记之前是否已经有通过i，j两点的直线 void init() { scanf("%d", &n); for(int i=1;i<=n;i++) { scanf("%lf%lf", &node[i].x, &node[i].y); } for(int i=1;i<=n;i++) { for(int j=i+1;j<=n;j++) { double k; if(fabs(node[j].x - node[i].x ) < esp) {//与y轴平行斜率不存在 k = 1e9+233; } else { k = (node[j].y - node[i].y) / (node[j].x - node[i].x); } bool flag = false; iter = temp.lower_bound({0, 0, k, false});//找i点形成的斜率相同的直线（会覆盖掉其他两点形成的直线） if(iter!=temp.end() && fabs(iter->k - k) < esp) { maps[make_pair(iter->b, j)] = 1;//记录被覆盖掉的直线 flag = true; } iter = temp.lower_bound({0, 0, k, true}); if(iter!=temp.end() && fabs(iter->k - k) < esp) { maps[make_pair(iter->b, j)] = 1; flag = true; } if(!flag) { if(maps[make_pair(i, j)]) { temp.insert({i, j, k, false}); } else { temp.insert({i, j, k, true}); } } else { temp.insert({i, j, k, false}); } } for(iter=temp.begin();iter!=temp.end();iter++) { if(!(iter->flag)) continue;//如果被覆盖跳过 ve.push_back(iter->k); } temp.clear(); } } int main() { // freopen("1.in", "r", stdin); init(); long long ans = 1ll * (ve.size()-1+1)*(ve.size()-1)/2;//假设任意两直线相交 sort(ve.begin(), ve.end()); long long now = 1; for(int i=0;i<ve.size()-1;i++) { if(ve[i] == ve[i+1]) { now++; } else { ans -= 1ll * (now - 1 + 1) * (now - 1) / 2;//减去两两平行不相交的直线 now = 1; } } ans -= 1ll * (now - 1 + 1) * (now - 1) / 2; printf("%lld", ans); return 0; }