The 13th Chinese Northeast Collegiate Programming Contest C. Line

Northeast Collegiate Programming Contest C. Line"/>

The 13th Chinese Northeast Collegiate Programming Contest C. Line

比赛链接

http://

题目链接

题目大意：

给n组二维坐标点，每一组两个点，组成一条直线。问有多少对直线存在公共点。

解题思路

1.如何保存直线信息。
用直线形式y=kx+b，维护k，b两个信息，虽然有一定精度损失，但是这个题也可以过。也可以考虑用两个的坐标gcd维护斜率信息，求出gcd之后标准化向量，如何维护b值。（斜率不存在单独考虑）
2.如何优化，不用O（nn)的复杂度。
首先对维护的直线排序，可以把斜率相同的直线排在一起，在斜率相同的直线中，存在重合和平行的直线，把b值作为第二排序量，可以保证重合的直线在一起。首先找到斜率相同的直线，计算更新一下答案ans（不考虑重合）。因为存在重合，在斜率相同的直线中，找到重合的直线，计算对数（cnt*(cnt-1)）/2，跟新ans。除开排序的时间，时间复杂度为O（n），总的时间复杂度为O（nlongn）

代码如下：

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include<set>
using namespace std;
const int N = 1e5 + 10;
const int INF = 0x3f3f3f3f;
struct node {int a, b;double c;node(int a, int b, double c) :a(a), b(b), c(c) {};node() {};bool operator<(const node& no)const {if (a == no.a&&b == no.b) {return c < no.c;}else if (a == no.a) {return b < no.b;}else return c < no.c;}bool operator==(const node&no)const {if (a == no.a&&b == no.b&&c == no.c)return true;return false;}
};
multiset<node>se;
int gcd(int a, int b)
{if (b == 0)return a;return gcd(b, a%b);
}
int main()
{int T;int n;scanf("%d", &T);while (T--) {se.clear();scanf("%d", &n);int x1, x2, y1, y2;for (int i = 0; i < n; i++) {scanf("%d%d%d%d", &x1, &y1, &x2, &y2);int gcd_ = gcd(abs(x2 - x1), abs(y2 - y1));int a = (x2 - x1) / gcd_;int b = (y2 - y1) / gcd_;if (a < 0) {a = -a;b = -b;}if (a == 0)b = abs(b);if (b == 0)a = abs(a);double c;if (x1 == x2)c = x1;else {double k = (y2 - y1+0.0) / (x2 - x1);c = y1 - k * x1;}se.insert(node{ a,b,c });}set<node>::iterator it = se.begin();set<node>::iterator temp = se.begin();set<node>::iterator temp1 = se.begin();long long num1 = 0, num2 = 0;long long ans = 0;long long res=n;while (it != se.end()) {num1 = 0;while (temp != se.end() && (*temp).a == (*it).a && (*temp).b == (*it).b) {temp++;num1++;//平行或者重合}res-=num1;ans += num1 * res;//重合没有计算temp1 = it;num2 = 1;temp1++;double d = (*it).c;while (temp1 != temp) {if ((*temp1).c ==d) {num2++;}else {ans += num2 * (num2 - 1) / 2;//计算重合个数直线对num2 =1;d = (*temp1).c;}temp1++;}it = temp;ans += num2 * (num2 - 1) / 2;}printf("%lld\n", ans);}return 0;
}

转载于:.html