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
更多推荐
The 13th Chinese Northeast Collegiate Programming Contest C. Line
发布评论