首先把所有直线表示出来.
然后按照斜率排序,把所有完全相同的删掉.
然后对每一个直线暴力找有多少个平行直线.
最坏复杂度O(n^4\log n^2),但这个题是随机数据,所以是O(n^2\log n^2).
下面的两个比较脚本都是让ds写的.
exp:(3.906 seconds)1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95std::array<int, 3> lineEquation(int x1, int y1, int x2, int y2) {
// 计算直线方程的系数
int a = y2 - y1;
int b = x1 - x2;
int c = x2 * y1 - x1 * y2;
// 计算系数的最大公约数
int g = __gcd(a, __gcd(b, c));
// 如果最大公约数不为0，用最大公约数化简系数
if (g != 0) {
a /= g;
b /= g;
c /= g;
}
// 保证a为非负，如果a为0则保证b为非负
if (a < 0 || (a == 0 && b < 0)) {
a = -a;
b = -b;
c = -c;
}
return {a, b, c};
}
/*
Prompt:我现在知道两个点的整数坐标，设为x[i],y[i],x[j],y[j],请给我写一个c++函数，返回array<int,3>,代表这个直线的解析式ax+by+c=0,注意上述运算必须全部整数运算，使用gcd函数
*/
vector<array<int,3>>vc;
// 比较函数，用于对直线按照斜率排序
bool cmp(const std::array<int, 3>& line1, const std::array<int, 3>& line2) {
int a1 = line1[0], b1 = line1[1], c1 = line1[2];
int a2 = line2[0], b2 = line2[1], c2 = line2[2];
// 处理垂直线的情况（b=0）
if (b1 == 0 && b2 == 0) {
// 两条都是垂直线，比较x轴截距
// 对于垂直线 ax + c = 0，x = -c/a
// 但由于a可能不同，我们比较 -c1*a2 和 -c2*a1
return (-c1 * a2) < (-c2 * a1);
}
if (b1 == 0) {
// line1是垂直线，应该排在所有非垂直线的右边（如果按斜率从小到大）
return false;
}
if (b2 == 0) {
// line2是垂直线，line1应该排在左边
return true;
}
// 一般情况：比较斜率 k = -a/b
// 为了避免浮点数，比较 a1*b2 和 a2*b1
// 因为 k1 = -a1/b1, k2 = -a2/b2
// 所以比较 k1 和 k2 等价于比较 -a1/b1 和 -a2/b2
// 即比较 a1*b2 和 a2*b1（注意符号）
// 由于我们想要按斜率从小到大排序，所以比较 a2*b1 和 a1*b2
long long cross1 = (long long)a2 * b1; // 对应 k2 的分母
long long cross2 = (long long)a1 * b2; // 对应 k1 的分母
if (cross1 != cross2) {
return cross1 > cross2; // 这样可以得到斜率从小到大的排序
}
// 如果斜率相同，比较y轴截距
// 截距 = -c/b
// 比较 -c1/b1 和 -c2/b2 等价于比较 -c1*b2 和 -c2*b1
long long intercept1 = (long long)(-c1) * b2;
long long intercept2 = (long long)(-c2) * b1;
return intercept1 < intercept2;
}
/*
Prompt:请写一个排序比较函数，对形如ax+by+c=0的直线按照"斜率"排序，需要排序的是vector<array<int,3>>,你的函数接口是char cmp(array<int,3>a,array<int,3>b){...}a[0]是上文的a,a[1]是b,a[2]是c
*/
i64 s[5010];
long long n,m,res;
//#define NaraFluorine
int main(){
n=2500;
s[0]=290797;
for(int i=1;i<=2*n;++i){
s[i]=s[i-1]*s[i-1]%50515093;
}
for(int i=1;i<=2*n;++i){
s[i]=s[i]%2000-1000;
}
for(int i=1;i<=n;++i){
for(int j=i+1;j<=n;++j){
int a,b,c;
vc.push_back(lineEquation(s[i*2-1],s[i*2],s[j*2-1],s[j*2]));
}
}
sort(vc.begin(),vc.end(),cmp);
m=unique(vc.begin(),vc.end())-vc.begin();
for(int i=0;i<m;++i){
int ttmp=i;
while(ttmp+1<m&&vc[ttmp][0]==vc[ttmp+1][0]&&vc[ttmp][1]==vc[ttmp+1][1])ttmp++;
res+=m-ttmp-1;
}
fout<<m<<"\n";
fout<<res*2;
return 0;
}