C小加

大意：兩個垂直于x軸的直線lx和rx圍成的區(qū)域。有n條直線穿過這片區(qū)域，每條直線yi=kxi+b，給出k和b。求直線把這個區(qū)域分成了幾個部分。三條直線不會交于一點（包括：兩個垂直于x軸的直線）。

畫圖可以找出一種關(guān)系，分成的區(qū)域數(shù)=交點數(shù)+線段數(shù)+1；對左端點從大到小排序，然后對右端點求逆序數(shù)，逆序數(shù)就是交點數(shù)，線段數(shù)已知，空間數(shù)就出來了。

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXM=30004;
const int INF=0x7fffffff-1;
typedef struct
{
    int y1,y2;
}Line;
Line line[MAXM];
int temp1[MAXM/2+1];
int temp2[MAXM/2+1];
int cnt;
bool cmp(Line l1,Line l2)
{
    return l1.y1>l2.y1;
}
void merge(int start,int mid,int end)
{
    int n1,n2;
    n1=mid-start+1;
    n2=end-mid;
    for(int i=0;i<n1;i++)
    temp1[i]=line[start+i].y2;
    for(int i=0;i<n2;i++)
    temp2[i]=line[mid+i+1].y2;
    temp1[n1]=-INF;
    temp2[n2]=-INF;
    for(int k=start,i=0,j=0;k<=end;k++)
    {
        if(temp1[i]>=temp2[j])
        {
            line[k].y2=temp1[i];
            i++;
        }
        else
        {
            cnt+=n1-i;//求逆序數(shù)
            line[k].y2=temp2[j];
            j++;
        }
    }

}
//歸并排序
void mergesort(int start,int end)
{
    if(start>=end) return;
    int mid=(end+start)/2;
    mergesort(start,mid);
    mergesort(mid+1,end);
    merge(start,mid,end);

}

int main()
{
    int lx,rx;
    while(scanf("%d%d",&lx,&rx)!=EOF)
    {
        cnt=0;
        int n,k,b;
        scanf("%d",&n);
        for(int i=0;i<n;i++)
        {
            scanf("%d%d",&k,&b);
            line[i].y1=lx*k+b;
            line[i].y2=rx*k+b;

        }
        sort(line,line+n,cmp);//對左端點從大到小排序
        mergesort(0,n-1);
        printf("%d\n",cnt+n+1);//空間數(shù)=交點數(shù)+線段數(shù)+1

    }
    return 0;
}