HDU 3465 Life is a Line 樹狀數組求逆序數

Life is a Line

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/65536 K (Java/Others)

Total Submission(s): 192 Accepted Submission(s): 71

Problem Description There is a saying: Life is like a line, some people are your parallel lines, while others are destined to meet you. Maybe have met, maybe just a matter of time, two unparallel lines will always meet in some places, and now a lot of life (i.e. line) are in the same coordinate system, in a given open interval, how many pairs can meet each other?

Input There are several test cases in the input. Each test case begin with one integer N (1 ≤ N ≤ 50000), indicating the number of different lines. Then two floating numbers L, R follow (-10000.00 ≤ L < R ≤ 10000.00), indicating the interval (L, R). Then N lines follow, each line contains four floating numbers x1, y1, x2, y2 (-10000.00 ≤ x1, y1, x2, y2 ≤ 10000.00), indicating two different points on the line. You can assume no two lines are the same one. The input terminates by end of file marker.

Output For each test case, output one integer, indicating pairs of intersected lines in the open interval, i.e. their intersection point’s x-axis is in (l, r).

Sample Input 3 0.0 1.0 0.0 0.0 1.0 1.0 0.0 2.0 1.0 2.0 0.0 2.5 2.5 0.0

Sample Output 1

Author 題目大意： 給出  一個區間  （ l  r），給出 n條直線，問這些直線有多少交點在區間内。 思路; 我們先求出給出每條直線在  l   r  上交點，如果   兩條直線相交，那麼    a  直線在 l  上的交點 在  b  直線在  l  上的交點下面  并且，a 直線在 r 上的交點在  b 直線與 r  交點的上方，或者是反過來，是以想到用逆序數來解決這個問題。 我們首先按照在  l  上交點 從小到大排序，然後編上序号，按照r上的順序，從大到小排序，統計就可以了。 特殊考慮的地方： 直線和 y 軸平行。 實話，printf  比 cout 快 AC代碼： #include<iostream> #include<algorithm> #include<string.h> #include<stdio.h> using namespace std; struct qqq { double ll; double rr; int pos; }qq[50005]; bool cmp1(const qqq &a,const qqq &b) { if(a.ll==b.ll) return a.rr<b.rr; return a.ll<b.ll; } bool cmp2(const qqq &a,const qqq &b) { if(a.rr==b.rr) { return a.ll>b.ll; } return a.rr>b.rr; } int a[50005]; int MAXN=50005; int lowbit(int x) { return x&(-x); } void add(int x,int add) { while(x<=MAXN) { a[x]+=add; x+=lowbit(x); } } int get_sum(int x) { int ret=0; while(x!=0) { ret+=a[x]; x-=lowbit(x); } return ret; } int main() { int n; double l,r; double x1,y1,x2,y2; double k,b; while(~scanf("%d",&n)) { int t=0; int tt=0; scanf("%lf%lf",&l,&r); for(int i=1;i<=n;i++) { scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2); if(x1==x2) { if(x1>l&&x1<r) { tt++; } continue; } k=(y2-y1)/(x2-x1); b=y1-k*x1; qq[t].ll=l*k+b; qq[t++].rr=r*k+b; } sort(qq,qq+t,cmp1); for(int i=0;i<t;i++) { qq[i].pos=i+1; } sort(qq,qq+t,cmp2); memset(a,0,sizeof(a)); int ans=0; for(int i=0;i<t;i++) { add(qq[i].pos,1); ans+=get_sum(qq[i].pos-1); } printf("%d\n",ans+tt*t); } }