C小加

大意：两个垂直于x轴的直线lx和rx围成的区域。有n条直线穿过这片区域，每条直线yi=kxi+b，给出k和b。求直线把这个区域分成了几个部分。三条直线不会交于一点（包括：两个垂直于x轴的直线）。

画图可以找出一种关系，分成的区域数=交点数+线段数+1；对左端点从大到小排序，然后对右端点求逆序数，逆序数就是交点数，线段数已知，空间数就出来了。

#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;//求逆序数
            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);//空间数=交点数+线段数+1

    }
    return 0;
}