题意：在x=a,x=b之间的区域，有n条直线，问区域被划分成几块。
思路：把左边排序，每次插入一条线，看有几个交点，每有一个比它大的数就有一个交点，ans += 交点数 + 1（ans初始化为1），查询比它大的数，容易想到用线段树，之前要把右边的点离散下（有负数，线段树不好搞）
#include<stdio.h> #include<iostream> #include<string.h> #include<string> #include<stdlib.h> #include<math.h> #include<vector> #include<list> #include<map> #include<stack> #include<queue> #include<algorithm> #include<numeric> #include<functional> using namespace std; typedef long long ll; #define lson(x) 2*x #define rson(x) 2*x+1 const int maxn = 3e4+5; int vis[maxn],pre[maxn],next[maxn]; map<int,int> ma; struct dat { int x,y; }nod[maxn]; vector<int> v; struct data { int l,r,num; }node[maxn*4]; void pushup(int cnt) { node[cnt].num = node[lson(cnt)].num + node[rson(cnt)].num; } void build(int x,int y, int cnt) { node[cnt].l = x; node[cnt].r = y; if(x == y) { node[cnt].num = 0; return; } int mid = (x+y) / 2; build(x,mid,lson(cnt)); build(mid+1,y,rson(cnt)); pushup(cnt); } void add(int x,int y,int cnt,int val) { if(x == node[cnt].l && y == node[cnt].r) { node[cnt].num += val; return; } int fa = 2*cnt; if(x <= node[fa].r) { if(y <= node[fa].r) add(x,y,fa,val); else add(x,node[fa].r,fa,val); } fa++; if(y >= node[fa].l) { if(x >= node[fa].l) add(x,y,fa,val); else add(node[fa].l,y,fa,val); } pushup(cnt); } int fid(int x,int y,int cnt) { if(x == node[cnt].l && y == node[cnt].r) { return node[cnt].num; } int fa = 2*cnt; int tp = 0; if(x <= node[fa].r) { if(y <= node[fa].r) tp += fid(x,y,fa); else tp += fid(x,node[fa].r,fa); } fa++; if(y >= node[fa].l) { if(x >= node[fa].l) tp += fid(x,y,fa); else tp += fid(node[fa].l,y,fa); } return tp; } int cmp(const dat &a,const dat &b) { if(a.x == b.x) return a.y < b.y; else return a.x < b.x; } int main(void) { int a,b,k,n,bb,m,i,j; while(scanf("%d%d",&a,&b)!=EOF) { scanf("%d",&m); v.clear(); for(i = 0; i < m; i++) { scanf("%d%d",&k,&bb); nod[i].x = k * a + bb; nod[i].y = k * b + bb; v.push_back(nod[i].y); } ma.clear(); sort(nod,nod+m,cmp); sort(v.begin(),v.end()); int cnt = 1; for(i = 0; i < m; i++) { if(i == 0) ma[v[i]] = cnt++; else if(v[i] != v[i-1]) ma[v[i]] = cnt++; } cnt--; build(1,cnt,1); int ans = 1; for(i = 0; i < m; i++) { if(ma[nod[i].y] < cnt) ans += 1+fid(ma[nod[i].y]+1,cnt,1); else ans++; add(ma[nod[i].y],ma[nod[i].y],1,1); } printf("%d\n",ans); } return 0; }
