一开始的想法很简单，本想求出所有直线的交点，然后判断；结果一开数据量10000，超时啊！好吧，用了逆序对。
将每条直线与L和R的的交点求出，分别放在结构体数组的P的下，x和y中，然后根据题意就是求线段的交点个数，也就是求
结构体数组的逆序对的个数。
View Code
1 #include<stdio.h>
2 #include<math.h>
3 #include<stdlib.h>
4 #define N 10001
5
6 typedef struct
7 {
8 double x,y;
9 }Node;
10 Node p[N];
11 long long count;
12 double a[N],b[N],c[N],d[N],k[N];
13 double l,r;
14
15 void Mergerarray(int first, int mid, int last)
16 {
17 int i,j,k;
18 int n1 = mid - first + 1;
19 int n2 = last - mid;
20 double L[n1+1],R[n2+1];
21
22 for(i=0; i<n1; i++)
23 L[i] = p[first + i].y;
24 for(j=0; j<n2; j++)
25 R[j] = p[mid + 1 + j].y;
26
27 i = j = 0;
28 L[n1] = 1.7e+300;
29 R[n2] = 1.7e+300;
30 for(k = first; k <= last; k++)
31 {
32 if(L[i] <= R[j])
33 {
34 p[k].y = L[i++];
35 }
36 else
37 {
38 count += (long long)(n1-i);
39 p[k].y = R[j++];
40 }
41 }
42
43 }
44
45 void Mergersort(int first, int last)
46 {
47 int mid;
48
49 if(first < last)
50 {
51 mid = (first + last)/2;
52 Mergersort(first, mid);
53 Mergersort(mid+1, last);
54 Mergerarray(first, mid, last);
55 }
56 }
57
58 int cmp(const void *a, const void *b)
59 {
60 if( ((Node *)a)->x > ((Node *)b)->x )
61 return 1;
62 else if( fabs( ((Node *)a)->x-((Node *)b)->x) < 0.00000001 && ((Node *)a)->y > ((Node *)b)->y)
63 return 1;
64 return -1;
65
66 }
67
68 int main()
69 {
70 int i,j,ncases;
71
72 while(scanf("%d",&ncases) != EOF)
73 {
74 for(i = 0; i < ncases; i++)
75 {
76 scanf("%lf%lf%lf%lf",&a[i],&b[i],&c[i],&d[i]);
77 k[i] = (d[i]-b[i])/(c[i]-a[i]);
78 }
79 scanf("%lf%lf",&l,&r);
80 for(i = 0; i < ncases; i++)
81 {
82 p[i].x = k[i]*(l-a[i])+b[i];
83 p[i].y = k[i]*(r-a[i])+b[i];
84 }
85 count = 0LL;
86 qsort(p,ncases,sizeof(Node),cmp);
87
88 Mergersort(0,ncases-1);
89
90 printf("%lld\n",count);
91 }
92
93 return 0;
94 } 坐标转化好以后使用归并排序的模板直接套上就可以了。
转载于:https://www.cnblogs.com/cn19901203/archive/2012/08/16/2641970.html