http://acm.hdu.edu.cn/showproblem.php?pid=3465太弱了，第一次聽說逆序對數，這題判斷線段相交的對數，可以轉換到逆序對數來做。而逆序對數可以修改一下歸并排序來實現，只要n logn的時間復雜度。大致的意思見下圖：
 右邊有多少對逆序對數，就是有多少個交點！
  hdu_3465
1 #include<iostream>
2#include<cstdio>
3#include<cmath>
4#include<algorithm>
5#include<cstring>
6#include<complex>
7using namespace std;
8typedef complex<double> point;
9
10const int maxn = 50005;
11const double eps = 1e-8;
12
13struct line
14 {
15 point a, b;
16  line( ){ }
17 line( point u, point v ) : a( u ), b( v ){ }
18 };
19
20struct node
21{
22 double yl, yr;
23 int id;
24}h[maxn];
25
26int A[maxn], B[maxn], C[maxn];
27double hr[maxn];
28
29int dblcmp( double x ) { return ( x < -eps ? -1 : x > eps ); }
30double operator ^( const point & p1, const point & p2 ) { return imag( conj( p1 ) * p2 ); }
31double operator &( const point & p1, const point & p2 ) { return real( conj( p1 ) * p2 ); }
32
33point operator * ( const line l0, const line l1 )
34{
35 double t = l0.a - l1.a ^ l0.b - l1.a;
36 double s = l0.b - l1.b ^ l0.a - l1.b;
37 return l1.a + ( l1.b - l1.a ) * t / ( t + s );
38}
39
40bool cmp( const node & a, const node & b )
41{
42 if( dblcmp( a.yl - b.yl ) != 0 ) return a.yl < b.yl;
43 return a.yr < b.yr ;
44}
45
46bool cmp1( int x, int y )
47{
48 if( dblcmp( h[x].yr - h[y].yr ) != 0 ) return h[x].yr < h[y].yr;
49 return h[x].yl < h[y].yl;
50}
51
52int TimeOfSort( int l, int r )
53{
54 int c = 0;
55 if( l < r )
56 {
57 int mid = ( l + r ) >> 1;
58 c = TimeOfSort( l, mid ) + TimeOfSort( mid + 1, r );
59 int i = l, k = l, j = mid + 1;
60 while( i <= mid || j <= r )
61 {
62 if( i <= mid && ( j > r || A[i] <= A[j] ) )
63 {
64 B[k] = A[i];
65 ++i;
66 }
67 else
68 {
69 c += mid - i + 1;
70 B[k] = A[j];
71 ++j;
72 }
73 ++k;
74 }
75 for( i = l; i <= r; ++i )
76 A[i] = B[i];
77 }
78 return c;
79}
80
81int main( )
82{
83 int n, cnt1, cnt2;
84 double l, r, x1, y1, x2, y2;
85 //freopen("life.in","r",stdin);
86 //freopen("life.out","w",stdout);
87 while( scanf("%d", &n) != EOF )
88 {
89 scanf("%lf%lf",&l,&r);
90 line Ll = line( point( l, 0 ), point( l, 1000 ) );
91 line Lr = line( point( r, 0 ), point( r, 1000 ) );
92 cnt1 = cnt2 = 0;
93 for( int i = 0; i < n; i++ )
94 {
95 scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
96 line L = line( point( x1, y1 ), point( x2, y2 ) );
97 if( dblcmp( real( L.a ) - real( L.b ) ) == 0 )
98 {
99 if( dblcmp( real( L.a ) - l ) > 0 && dblcmp( r - real( L.b ) ) > 0 )cnt2++;
100 }
101 else
102 {
103 point p = L * Ll;
104 h[cnt1].yl = imag( p );
105 p = L * Lr;
106 h[cnt1].yr = hr[cnt1] = imag( p );
107 //h[cnt1].id = cnt1;
108 cnt1++;
109 }
110 }
111 sort( h, h + cnt1, cmp );
112 for( int i = 0; i < cnt1; i++ )
113 h[i].id = i, A[i] = i;
114 sort( A, A + cnt1, cmp1 );
115 int ans = TimeOfSort( 0, cnt1 - 1 );
116 ans = ans + cnt2 * cnt1;
117 printf("%d\n",ans);
118 }
119 return 0;
120}
121
|