点我看题
题意:给出两条与y轴平行的直线,选中由这两条直线组成的区域,然后再有n条y=k*x+b的直线经过这个区域,且三条直线(包括与y轴平行的直线)不会交于一点,问这n条直线最多能把平面分成多少个区域.
分析:n条直线能把某一平面分成的区域数=直线在总区域内的交点数+直线数+1,那么这个题就转化为了求n条直线在平面内求交点数的问题了,那么如何求这个交点数呢,我们可以先举个例子,假设经过按照左边从小到大排序后,左边点的顺序从下到上对应123456,而右边从下到上为246135(可以自行画一个图),对于1,左边下面没有比它小的,记为0,对于2,左边下面1比他小,右边上面1比它大,记为1(1),对于3,左边下面1和2比它小,右边上面没有把它小的,记为0,对于4,左边下面1和2和3比他小,右边上面1和3比它小,记为2(1,3),同理5,记为0,6记为3(1,3,5),所以交点个数为0+0+1(1)+0+2(1,3)+3(1,3,5)=5,分出来的区域个数为5+6+1=12.其实转换过来就是将左边按从小到大排序,最后求右边的逆序数就好.
参考代码:
#include<cstdio> #include<cmath> #include<cstring> #include<algorithm> #include<iostream> using namespace std; const int maxn = 3e4+10; int l,r,n; struct Node{ int y1,y2; }; Node pp[maxn]; int k,b; int ans; int tmp[maxn]; bool cmp( Node p, Node q) { return p.y1 < q.y1; } void Merge( int l, int mid, int r) { int i = l; int j = mid+1; int k = l; while( i <= mid && j <= r) { if( pp[i].y2 > pp[j].y2) { tmp[k++] = pp[j++].y2; ans += mid-i+1; } else tmp[k++] = pp[i++].y2; } while( i <= mid) tmp[k++] = pp[i++].y2; while( j <= r) tmp[k++] = pp[j++].y2; for( int i = l; i <= r; i++) pp[i].y2 = tmp[i]; } void MergeSort( int l, int r) { if( l < r) { int mid = (l+r)>>1; MergeSort(l,mid); MergeSort(mid+1,r); Merge(l,mid,r); } } int main() { while( ~scanf("%d%d",&l,&r)) { scanf("%d",&n); for( int i = 0; i < n; i++) { scanf("%d%d",&k,&b); pp[i].y1 = k*l+b; pp[i].y2 = k*r+b; } sort(pp,pp+n,cmp); ans = 0; MergeSort(0,n-1); printf("%d\n",ans+n+1); } return 0; }